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.
Best Answer
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.