# Proof that if all vertices have degree at least two then $G$ contains a cycle

Prove that if all vertices have degree at least two then $$G$$ contains a cycle.

Here is the proof, but please correct me if wrong :

We assume $$G$$ is simple and let $$P$$ be the longest path $$=v_0v_1v_2\ldots v_{a-1}v_a$$.

As it is given that the degree of $$v_a$$ is even ,then $$v_a$$ must have $$\mathbf{2}$$ neigbors; one of them is $$v_{a-1}$$ and the other must be any $$v$$ in the Graph $$G$$, so $$v=v_i$$, where $$i$$ is any integer between $$0$$ and $$a-2$$ : $$0\leq i \leq(a-2)$$ #

Please correct me if I am wrong, and sorry for any mistakes.

• You can omit the [incorrect] claim that the degree of $v_a$ is even... you already know it has at least two neighbors Jun 22 '15 at 17:32
• Put the whole subscript in curly braces: to get $v_{a-1}$ use v_{a-1}. Jun 22 '15 at 17:37

The idea is right, but there’s a small mistake, and there are a couple of places where you could be a little clearer. You don’t know that the degree of $v_a$ is even: it’s quite possible that $\deg v_a$ is odd. You do know, however, that $\deg v_a\ge 2$, which is all that you need. Then you can say that $v_a$ must be adjacent to at least one vertex $v$ that is not $v_{a-1}$. At that point you really should say a little more than you did: you should point out that if $v\notin\{v_0,\ldots,v_{a-2}\}$, then we could extent the path $P$ to $v$. However, $P$ was chosen to be of maximal length, so this is impossible, and therefore $v\in\{v_0\ldots,v_{a-2}\}$. Thus, if $v=v_i$, then $v_iv_{i+1}\ldots v_av_i$ is a cycle.
• @John: I’m not sure what you mean. The only place where a contradiction is involved is when we observe that $v$ is one of the vertices $v_0,\ldots,v_{n-2}$: if it were not, the path $v_0\ldots v_nv$ would contradict the choice of $P$ as a maximal path. There’s no contradiction at the end, though: there we simply have the desired cycle. Jun 23 '15 at 19:36
I guess you assume that $G$ is a finite graph. What is the maximum possible number of edges that a spanning forest of $G$ can have? What is the minimum possible number of edges can $G$ have?
• Let $n$ be the number of vertices of $G$. If $G$ has no cycle, then $G$ is a forest, then $G$ has at most $n-1$ edges. If every vertex of $G$ is of degree at least $2$, then $G$ has at least $n$ edges. Do you see my point now? Jun 23 '15 at 3:56