Cycle in a graph. Given an non oriented graph $G=(V,E)$, prove that if $|V| \geq 3$ and there exists an unique $v_0 \in V  $ s.t. $d(v_0)=1$ then the graph $G$ contains a cycle.
Using the hand-shaking lemma we have that $ \sum_{v \in V} d(v)=2|E| \rightarrow \sum _{v\in V\setminus{v_0}}d(v) + d(v_0)=\sum _{v\in V\setminus{v_0}}d(v)+1=2|E| $ from where it follows that we have atleast one more vertice of odd degree. How do I prove that $G$ contains a cycle?
 A: Let's just follow our nose.
We start with a vertex $v_1$ with $\deg v_1=1$. Let $v_2$ be its neighbour. As $\deg v_2>1$, we know $v_2$ has another neighbour $v_3\neq v_1$.
Likewise, $v_3$ has a neighbour $v_4\neq v_2$. Also, $v_4\neq v_1$, as $v_1$ is a leaf. Now $v_4$ has a neighbour that is not $v_1$ or $v_3$. This neighbour could be $v_2$ (in which case we have a cycle), or it could be another vertex $v_5$.
So we get a path $v_1,v_2,v_3,\dots$, which (if $G$ is finite) has to repeat a vertex eventually. When it does, we get a cycle.
The claim is false when $G$ is infinite, e.g. take your vertices to be $\mathbb N$, and draw an edge between $m$ and $n$ iff $|m-n|=1$.
A: I don't think you really need hand - shaking lemma.
From $d(v_0)=1$ there exists $v_1 $connected to it. Now for vertex different from $ v_0$ if you have anny neighbour you have at least two of them. So there exists $v_2$ connected to $v_1$ with degree at least two...
But as graph is finite this has to stop at some $v_n$ from which I believe you can deduce existence of a cycle.
