Let $G$ be a graph such that all its vertices have degree 2. Prove that
$G$ is a union of pairwise disjoint cycles.
This is Exercise 4.1.4 in the book Problem-Solving Methods in Combinatorics by Pablo Soberón.
Since exercises do not have any solutions in the book, I came here to ask for help.
I was thinking of using mathematical induction, since most basic graph properties I saw can be proven using induction. So let's induct on the number of vertices the graph has.
- Base case: if the graph has one vertex, then the problem is obvious (the graph must be a loop, which is a cycle)
- Induction step: I don't have any ideas how to do this. I was thinking of considering a subgraph $G'$ that has less than $n$ vertices and also all of its vertices have degree 2.
Please help me! Thank you in advance!
Best Answer
Pick a vertex $v$.
If it is only connected by a loop with itself, this constitutes a cycle. If we remove $v$ and its loop, we obtain a smaller graph, which by induction hypothesis constsist of disjoint cyces.
If $v$ is connected only to one other vertex $w$ by two edges, then $v,w$ form a cycle. Removing, we obtain a smaller graph, which again consists of disjoint cycles
Finally, if $v$ has two isinct neighbours $u,w$, remove $v$ and edges $vu$, $vw$, and add an edge $uw$. Apply induction hypothesis again and argue that reinserting $v$ between $u$ and $w$ gives you a cycle again.