2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ What are $K_n$ and $C_n$? $\endgroup$ Aug 29, 2020 at 19:11
  • $\begingroup$ @Taroccoesbrocco: The complete graph on $n$ vertices and the cyclic graph on $n$ vertices, respectively. $\endgroup$ Aug 29, 2020 at 20:10
  • $\begingroup$ Thank you Brian, this is precisely what was meant. $\endgroup$
    – Dovendyr
    Aug 30, 2020 at 8:51
  • $\begingroup$ No, and I am not sure it is true either. The problem statement says "is it true that..." $\endgroup$
    – Dovendyr
    Sep 5, 2020 at 12:02
  • $\begingroup$ I am sorry, asked the teacher and saw it was untrue. Can you explain that instead please? $\endgroup$
    – Dovendyr
    Sep 5, 2020 at 12:20

1 Answer 1

0
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.