Partition Graph Challenging Question

Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles?

K_m,n,r means 3-Partite Complete Graph with m, n, and r sections.

a) K₇

b) K₁₂

c) K_3,3,3

d) K_5,5,5

i think the (d) is correct, but doesn't have any idea.

Answer 1

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.