Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
7  
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
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. –  Steven Stadnicki Apr 5 '12 at 20:25

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.