[Math] A graph whose vertices all have degree $2$ must contain a cycle

graph theory

I've been working on some beginner graph theory, and I was having some
funky issues with this particular problem. Consider a graph $G$ such that
for all $x \in V(G),\, \deg(x) = 2.$ I want to prove that this implies that
a cycle exists in this graph.

I imagined the best place to first start with
a problem like this is to design an assume for the sake of contradiction
where there is no cycle in $G$. Consider the vertex $x_1 \in V(G).$ We know
that there exists an edge going from $x_1$ to some $x_2 \in V(G).$ Similarly,
there exists an edge going from $x_2$ to some $x_3 \in V(G),$ but $x_3$ cannot
have an edge going towards $x_1$ because that would generate a cycle. We
continue inductively such that for each $x_k$, it cannot have an edge
pointing back at $x_1,x_2,…,x_{k-2}$ due to the fact that this would induce
a cycle in the graph. Hence, I'm left with the path $x_1,…,x_n$ where
$|V(G)| = n.$ However, now I am not sure what to do here. Any suggestions?

Best Answer

You already have your contradiction. In your path $x_1 \cdots x_n$, the degree of $x_1$ and $x_n$ are $1$, contradicting the fact that $\deg(x) = 2$ for all $x$. Your proof can be cleaned up a little bit to show that every tree (defined as a connected cycle-free graph) has at least two leaves (vertices of degree $1$), of which your problem is a simple corollary.

Another, perhaps more convincing, way to see this contradiction is to not stop at all. Suppose we had a graph without a cycle such that all vertices had degree $2$. Pick an arbitrary vertex $x_0$.

  1. Since $x_0$ has degree $2$, it must be connected to another vertex, say $x_1$.
  2. Since $x_1$ has degree $2$, it must be connected to some vertex other than $x_0$, say $x_2$.
  3. Since $x_2$ has degree $2$, it must be connected to some vertex other than $x_1$, say $x_3$. Now $x_3$ cannot be equal to $x_0$, or we would have a cycle.

Inductively, we see that for each $x_k$ in our path, we can find a unique vertex $x_{k+1}\neq x_\ell$ for $\ell \le k$, so we must have an infinite sequence of vertices. This contradicts the fact that our graph is finite.

Finiteness is a necessary assumption here, because otherwise we could extend the path forwards and backwards from $x_0$ to get a doubly infinite path graph. This is a perfectly valid infinite graph which satisfies your assumptions. In fact, the cycle graphs and the infinite path graph (which is just an infinitely large cycle) are the only (connected) graphs which satisfy the $\deg(x) = 2$ condition.

Related Question