3
$\begingroup$

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?

  • 2
    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.2012-04-05

1 Answers 1

2

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, 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.