Exercise 1.1.17 from West

Question

Here is exercise 1.1.17 from Introduction to Graph Theory by Douglas B. West

1.1.17. Prove that $K_n$ has three pairwise-isomorphic subgraphs such that each edge of $K_n$ appears in exactly one of them if and only if n is congruent to $0$ or $1$ modulo $3$.

I am trying to formalize a proof for this exercise, but struggle simplifying my arguments. I would appreciate if you could pinpoint where I should be clearer or where I am wrong. Here is what I've sketched so far.

Sketch

The number of edges for any given n-vertex clique $K_n$ is $n(n-1)/2$.

If $3 | n+1$ then $3\nmid n(n-1)$. Therefore, $e(K_n)$ is divisible by three if and only if $n+1$ is not divisible by three.

To us this means that the edge set of a n-vertex clique can be partitioned into three equally sized subsets of edges given that $n(n-1)$ is divisible by three.

First, consider the case where $n$ is divisible by three. Now, imagine we are reconstructing a clique with three pairwise isomorphic subgraphs. And observe how the following algorithm induces $K_n$.

1. Draw three copies of $K_{n/3}$ which are disjoint from one another.

2. Pair every copy and add an edge within a pair if two vertices are not adjacent to each other.

And so we've induced $K_n$. Because copies are isomorphic with respect to one an other, then all pair of copies must also be isomorphic with respect to one another. Therefore, in the case where $n$ is divisible by three then the claim in 1.1.17 is shown to be true.

The reasoning for the case where $n+1$ is divisible by three is corollary to this framework so I will not highlight it.

Answer 1

There is a simpler way to do this. You can partition, iff $n \equiv_3 0$ or $n \equiv_3 1$, the set $E(K_n)$ into $3$ subgraphs where each of the $3$ subgraphs consists of

• a clique on $\lceil \frac{n}{3} \rceil$ vertices,
• and a complete bipartite graph with $\lfloor \frac{n}{3} \rfloor$ vertices on each side, on the remaining $2 \lfloor \frac{n}{3} \rfloor$ vertices.

For $n \equiv_3 0$:

1. Write the vertices of $K_n$ as $v_1,\ldots, v_n$
2. Let $H_i; i =0,1,2$ be the graph where $v_r$ and $v_s$ form an edge iff $r+s \equiv_3 i$. Then check that every edge of $K_n$ is in exactly one of the $3$ graphs $H_i$; $i=0,1,2$, and that each of the $H_i$s consists of a clique on $n/3$ vertices plus a complete bipartite graph, with $n/3$ vertices on each side. on the remaining $2n/3$ vertices. So $H_0,H_1,H_2$ are indeed isomorphic to each other and their edge-set partitions $K_n$.

For $n \equiv_3 1$:

1. Then $n-1 \equiv_3 0$. Partition $E(K_{n-1})$ then, into $H_0,H_1,H_2$ as above in this answer.
2. Let $H'_0$ be the graph where there is an edge between $v_n$ and every vertex $v_s$ where $s \equiv_3 0$. Then $H'_0$ consists of a clique on $1+(n-1)/3$ $=\lceil \frac{n}{3}\rceil$ vertices plus a complete bipartite graph, with $(n-1)/3 =\lfloor\frac{n}{3}\rfloor$ vertices on each side. on the remaining $2(n-1)/3 = 2\lfloor \frac{n}{3}\rfloor$ vertices.
3. Let $H'_1$ be the graph where there is an edge between $v_n$ and every vertex $v_s$ where $s<n$ and $s \equiv_3 1$. Then $H'_1$ consists of a clique on $1+(n-1)/3 =\lceil \frac{n}{3}\rceil$ vertices plus a complete bipartite graph, with $(n-1)/3=\lfloor \frac{n}{3}\rfloor$ vertices on each side. on the remaining $2(n-1)/3=2\lfloor\frac{n}{3}\rfloor$ vertices.
4. Let $H'_2$ be the graph where there is an edge between $v_n$ and every vertex $v_s$ where $s<n$ and $s \equiv_3 2$. Then ... you can take it from here. So here $H'_0,H'_1$, and $H'_2$ are $3$ isomorphic subgraphs of $K_n$ whose edge-set partitions $K_n$.

Answer 2

Consider a complete graph $K_n=(V,E)$ where $n\gt1$. If $n\not\equiv2\pmod3$ there is a permutation $\sigma$ of $V$ of order $3$ with at most one fixed point; the cycle decomposition of $\sigma$ consts of $k$ $3$-cycles if $n=3k$, or $k$ $3$-cycles and a $1$-cycle if $n=3k+1$. The permutation $\sigma$ of $V$ induces a permutation $\tau$ of $E$ which maps the edge $vw$ to the edge $\sigma(v)\sigma(w)$. Note that $\tau$ is a permutation of order $3$ with no fixed points, its cycle decomposition consisting entirely of $3$-cycles. Choose one edge in each $3$-cycle of $\tau$ and color it red. If an edge $e$ is colored red, then color $\tau(e)$ white and $\tau^2(e)$ blue. Thus each edge of $K_n$ has a unique color, red, white, or blue; so the graph $K_n$ is decomposed into a red graph, a white graph, and a blue graph. Finally, the permutation $\sigma$ maps the red graph isomorphically to the white graph, the white graph isomorphically to the blue graph, and the blue graph isomorphically to the red graph.