# Is a 2-regular graph the same as a single cycle?

When I was doing some graph theory problem, came to my mind this corollary:

Graph G is a single cycle if and only if $\displaystyle \forall_{v\in V[G]}\deg(v)=2$

I don't know whether I make myself clear but I mean graphs which can be represented by polygons. Is it true, or maybe I am wrong? How to prove this?

-
It might also be a union of disjoint cycles. –  MJD Apr 4 '12 at 16:03
ok, but if I consider only connected graphs? you're right, I should write it in my hypothesis.. –  xan Apr 4 '12 at 16:18
It is true. The "only if" direction is trivial. To prove the "if" statement, choose a vertex and consider a path leaving this vertex. Make the path as long as possible. Where does it end? –  MJD Apr 4 '12 at 16:25
.. at the chosen vertex? because if $\forall{v\in V[G]}\deg(v)=2$ then when we leave this vertex we should could go back.. and in every vertex there is a situation that if we go into some vertex we have one possible way out? –  xan Apr 4 '12 at 16:38
Your theorem also needs the hypothesis that $G$ is finite; otherwise the graph whose vertices are the set $\mathbb{Z}$ with edges between $n$ and $n+1$ for all $n\in\mathbb{Z}$ is also a counterexample. –  Steven Stadnicki Apr 5 '12 at 20:25

You have the right general idea in your comment to Mark Dominus, but the details still require a bit of work. Here’s one way to fill them in. (Note that I’m assuming that $G$ is connected. If not, the same argument shows that it’s a union of disjoint cycles.)
Pick a vertex $v_0$. It has two neighbors; pick one of them and call it $v_1$. Suppose that for some positive integer $k$ you’ve picked distinct vertices $v_0,\dots,v_k$ in such a way that they form a path from $v_0$ to $v_k$. Now consider the edge incident at $v_k$ that does not go to $v_{k-1}$, and let $v_{k+1}$ be the vertex to which it does go. Note first that $v_{k+1}$ cannot be one of the vertices $v_1,\dots,v_{k-1}$: if $v_{k+1}$ is adjacent to $v_i$, say, where $1\le i<k$, then $v_i$ is adjacent to the three distinct vertices $v_{i-1},v_{i+1}$, and $v_{k+1}$, which is impossible. If $v_{k+1}\ne v_0$, the distinct vertices $v_0,\dots,v_{k+1}$ form a path from $v_0$ to $v_{k+1}$, and the inductive construction of our path can continue. Eventually, however, we run out of unused vertices, and at that point we must have $v_{k+1}=v_0$, so that in fact $v_0,\dots,v_k$ is a cycle of length $k+1$. If this cycle is all of $G$, we’re done. But this is clear: every edge incident at any of the vertices $v_0,\dots,v_k$ is already part of the cycle, so the cycle cannot be connected to any vertex of $G$ not already part of the cycle. Since $G$ is connected, there cannot be any vertices not already part of the cycle, and therefore $G$ is the cycle.