Any finite connected graph with every vertex has degree $\ge 2$ has a circuit

Question

Is my proof for the following statement correct?

Any finite connected graph with every vertex has degree $\ge 2$ has a circuit.

My attempt: Let $G$ be a finite connected graph. Let $|G|=n$. Suppose that degree of any vertex $\ge 2$. Now, pick any vertex $v_1$. By hypothesis $v_1$ must have at least two distinct edges incident on it; pick one, call it $e_1$. Call the end vertex of $e_1$ different from $v_1$ as $v_2$. Now pick an edge $e_2$ different from $e_1$ incident on $v_2$. Let $v_3$ be the end vertex of $e_2$ different from $v_2$. If there is an edge joining $v_3$ and $v_1$, we are done. If not, pick any edge $e_3$ different from $e_2$ incident on $v_3$ and repeat the previous argument. Now, we proceed by induction and find vertices $\{v_1 , v_2, \ldots, v_n , v_{n+1} \}$ such that there is an edge between $v_i$ and $v_{i+1}$. Since $G$ is connected, the component of $G$. containing $v_1$ which is a superset of $\{ v_1, v_2, \ldots , v_{n+1} \}$ is equal to $G$. So, $v_{n+1}=v_1$ and hence we are done.

Is this proof correct? Is there an easier way to do this?

Answer 1

There is no guarantee $v_{n+1}=v_1$. For example, take a "bow-tie" graph (i.e., two 3-cycles with a vertex in common) and start at $v_1$ any degree-2 vertex, $v_2$ the cutvertex and now only walk the other triangle for $v_3,v_4,v_5,v_6$.

Instead, note that $v_1,v_2,\dots,v_{n+1}$ are $n+1$ vertices from the set of $n$ vertices of $G$, so by pigeonhole there must be $1\leq i<j\leq n+1$ with $v_i=v_j$. By construction we know $j\neq i+1$ and so ...

Answer 2

Let $P:=v_0,\ldots,v_n$ be any maximal path in $G$. Since $P$ is maximal, $P$ cannot be extended. So every neighbour of $v_0$ must be a vertex in $P$. Since $d(v_0)>1$, there exists a vertex $v_k$ in $P$ such that $v_k \leftrightarrow v_0$ with $k>1$.

Let $\ell$ denote the least $k>1$ such that $v_k \leftrightarrow v_0$. Then the $v_0-v_{\ell}$ path on $P$ followed by the edge $v_{\ell}v_0$ is a cycle in $G$. $\blacksquare$

Answer 3

I think you have the right idea but the proof isn't quite correct because it's not necessarily the case that $v_{n+1}=v_1$. I'd go a little simpler.

Assume $\vert G \vert = n$. Start at $v_1$. Proceed inductively. If there are no unused edges from $v_m$, then you've necessarily been at both $v_m$ and its predecessor at least once before so you have a cycle. Otherwise, choose an unused edge from $v_m$ to reach vertex $v_{m+1}$. Continue until you've reached $v_{n+1}$. By the pigeonhole principle, two of your vertices $v_m, v_{m+k} ~(k \gt 1)$ must be the same, so again you have a cycle.