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

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?

• Simpler: assume the opposite. Then, G is a tree. A tree has at least one leave, which has degree 1. This is a contradiction. Jul 12, 2020 at 6:25
• Btw, you should either exclude or separately treat the empty graph and the graph with one vertex... Jul 12, 2020 at 6:31
• @NeitherNor I am trying to use this to prove that a tree with $n$ vertices has $n-1$ edges. Jul 12, 2020 at 7:38
• @NeitherNor there's nothing to prove in the case where $|G|=0$ and $|G|=1$ Jul 12, 2020 at 7:45

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 with $$v_i=v_j$$. By construction we know $$j\neq i+1$$ and so ...

• You need to be just a little careful to establish that there is an unused edge that allows you to continue the construction. Jul 12, 2020 at 6:25
• @RobertShore The OP's construction already established that. The only final touch in the "..." is a minimality argument to deal with the possible case $v_iv_{i+1}$ and $v_{j-1}v_j$ are the same edge.. Jul 12, 2020 at 6:31

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$$

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.