I've been working through some graph theory problems and recently encountered one which had me stumped. Fortunately, a solution was provided by my resource. Unfortunately, the solution does not seem intuitive to me at all.
"Suppose that every vertex of a loopless finite graph $G$ has degree at least 3. Prove that $G$ has a cycle of even length."
I've taken the following solution and broken it down into parts so I can better express my concerns at each point.
Solution:
-
Let $P$ be a maximal path in $G$ with $v$ is an endpoint of $P$.
-
Then $v$ has at least 3 neighbors on $P$.
-
Let $x$, $y$, $z$ be 3 such neighbors of $v$ in order on $P$.
-
Consider 3 $v$, $y$-paths: the edge $vy$; the edge $vx$ followed
by the $x$, $y$-path in $P$; and the edge $vz$ followed by the
$z$, $y$-path in $P$. -
These paths share only their endpoints, so the union of any 2 is a
cycle. -
By the pigeonhole principle, 2 of these paths have lengths with the
same parity (odd or even). -
The union of these 2 paths is an even cycle.
If anyone could help explain the intuition behind this solution to me, I would greatly appreciate it. First off, I never would have even tried starting with a maximal path had I been given this problem. Where does that intuition come from? How is this approach the most obvious? Also, I don't see how part 2 follows from part 1. I've drawn out a lot of test graphs and see that it's true, but the jump from part 1 to part 2 seems like a bit of a leap of logic to me.
Thanks!
Best Answer
The proof you have posted makes too many leaps, so do not fret that you cannot follow it. The jump from 1-2, is to my mind, the most important of the whole proof.
The idea of 1-> 2 is that all of the neighbours of $v$ must reside on a maximal path (notice the emphasis, there might be multiple such paths of equal length).
If there was some neighbour that was not on the path, then we could extend our maximal path, but we already assumed it to be the maximal, so it contradicts our assumption.
To make it more clear, consider a maximal path which we will denote as follows $v_0v_1v_2...v_k$ (notice that you called the last vertice $v$, but I will call it $v_k$)
$v_k$ must have at least 3 neighbours, since its degree is at least 3. But from the previous we have a restriction that since the path is maximal, all its neighbours must be on it (we argued that otherwise we could attach some node to the right, $v_{k+1}$, and thereby the path that we assumed to be the maximal, would not be maximal any more, a contradiction). So, we have a path that is of length at least 3.
I did not come up with this myself though, it was in my textbook. Hope this helps.