Prove that for n ≥ 3, $K_n$ is the union of cycles $C_3,\ldots,C_{n − 1}$, a path of length 2 and an edge.

Question

We managed to prove that $K_n$ and the union of cycles $C_3$ to $C_{n − 1}$ have same number of edges:

$ n \choose 2 $ = $\sum_{1}^{n-1}k = \frac{n(n-1)}{2}$

We know we need to prove it by induction, but the priority right now is to understand whether this condition (same number of edges) is sufficient to reply the questions. How can we arrange the cycles in a specific way without "breaking the rings", to make the complete graph $K_n$?

I read the following post but I don't really understand the proof: $K_n$ for odd $n$ $ϵ$ $Z_+$ is a disjoint union (of edges) of collections of Hamiltonian cycles

Answer 1

If a graph $G$ is decomposed into cycles and paths, then each cycle contributes $0$ or $2$ to the degree of each vertex of $G$, and each path contributes $0$ or $2$ to the degree of each vertex except its endpoints. Therefore, a graph which can be decomposed into two paths and a number of cycles can have at most four vertices of odd degree, namely the endpoints of the paths. Since every vertex of $K_n$ has odd degree when $n$ is even, it follows that the statement is false for all even $n\gt4$.

On the other hand, the statement is easily seen to be true for $n=3,4,5,7$. For instance, $K_7$ can be decomposed into $5$ cycles of lengths $3,3,4,5,6$ as follows. Call the vertices $A,B,C,D,E,F,G$; then the cycles are $ABDA$, $ACEA$, $AFCGA$, $BEGDFB$, $BCDEFGB$. (Of course you can break one of the $3$-cycles into a path of length $1$ and a path of length $2$.)

In fact, the statement seems to be true for all odd $n\ge3$. It follows from one of the general results of Darryn Bryant, Daniel Horsley, and William Pettersson in their 182-page paper Decomposition of complete graphs into cycles of arbitrary lengths that for odd $n\ge3$ the complete graph $K_n$ can be decomposed into a cycle of length $3$ and $n-3$ additional cycles of lengths $3,4,\dots,n-1$. Quoting their abstract:

We show that the complete graph on $n$ vertices can be decomposed into $t$ cycles of specified lengths $m_1,\dots,m_t$ if and only if $n$ is odd, $3\le m_i\le n$ for $i=1,\dots,t$, and $m_1+\cdots+m_t=\binom n2$.
We also show that the complete graph on $n$ vertices can be decomposed into a perfect matching and $t$ cycles of specified lengths $m_1,\dots,m_t$ if and only if $n$ is even, $3\le m_i\le n$ for $i=1,\dots,t$, and $m_1+\dots+m_t=\binom n2-\frac n2$.

I have not studied the proofs, which are long and complicated with many cases.