Q:

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles?
Km,n,r  means 3-Partite Complete Graph with m, n, and r sections.
a) K7
b) K12
c) K3,3,3
d) K5,5,5
i think the (d) is correct, but doesn't have any idea.

A:

The first two problems ask for Steiner Triple Systems.  It is known that a Steiner Triple System exists if and only if $n \equiv 1 \text{ or } 3 \pmod 6$.

For $K_7$ we have $7 \equiv 1 \pmod 6$, so one exists.  An example is drawn on the Wikipedia page (with triangles are drawn as lines):

(see also Fano plane).
For $K_{12}$ we have $12 \equiv 0 \pmod 6$, so none exist.
Another proof of its non-existence: (a) every vertex in $K_{12}$ has $11$ neighbors, (b) every  vertex in a triangle has $2$ neighbors.  So, if $v$ is a vertex in $K_{12}$, any decomposition divides the $11$ neighbors into pairs, but this is impossible since $11/2$ is not a whole number.
(Actually, this is part of how the $n \equiv 1 \text{ or } 3 \pmod 6$ condition comes about.  The other part is that $\binom{3}{2}$ divides $\binom{n}{2}$.)

The second two problems ask for the existence of a Latin square of order $n$.  Suppose $\{u_i\} \cup \{v_j\} \cup \{w_k\}$ is the vertex tripartition.  Take a Latin square of order $n$: if symbol $s$ occurs in cell $(r,c)$ then $\{u_r,v_c,w_s\}$ is a triangle.  Latin squares exist for all $n \geq 1$ (e.g. the Cayley table of $\mathbb{Z}_n$).
I'll do the $n=3$ case, the $n=5$ case is similar.
The entries of the Latin square
$$
\begin{bmatrix}
\color{red}{1} & \color{blue}{2} & 3 \\
2 & 3 & 1 \\
3 & 1 & \color{green}{2} \\
\end{bmatrix}
$$
can be written as an "orthogonal array":
$$\{\color{red}{(\overbrace{1}^{\text{row } 1},\overbrace{1}^{\text{col } 1},\overbrace{1}^{\text{sym } 1})},\color{blue}{(\overbrace{1}^{\text{row } 1},\overbrace{2}^{\text{col } 2},\overbrace{2}^{\text{sym } 2})},\ldots,\color{green}{(\overbrace{3}^{\text{row } 3},\overbrace{3}^{\text{col } 3},\overbrace{2}^{\text{sym } 2})}\}.$$
So in $K_{3,3,3}$, we have the decomposition
$$\big\{\color{red}{\{u_1,v_1,w_1\}}\color{blue}{\{u_1,v_2,w_2\}},\ldots,\color{green}{\{u_3,v_3,w_2\}}\big\}.$$
The Latin square properties ensure that no edge is used in two triangles: e.g. if $u_i v_j$ were used twice, then the would be two symbols in cell $(i,j)$ in the Latin square.

