Prove that a graph contains a loop whose length is an even number.

Question

Prove that if $G$ is a graph with minimum degree $\delta(G) \ge 3$, then it contains a loop whose length is an even number.

Answer 1

I assume that the graph is finite.

By finiteness there is a simple path $P$ of maximal length. By simple I mean that the path never meets the same vertex or the same edge twice.

Then consider one of the two end-vertices, say $v$, of the path. Exactly one of the edges adjacent to $v$ belongs to $P$ already. By assumption there are at least two other edges adjacent to $v$, say $e_1=\{v,v_1\}$ and $e_2=\{v,v_2\}$. By maximality, $P$ must have already met the vertices $v_1$ and $v_2$ earlier. Say $v_2$ is the latest one.

Therefore we have three paths to achieve $v\to v_2$:

• The edge $e_2$ alone;
• The edge $e_1$ followed by the part of $P$ that goes $v_1\to v_2$;
• The part of $P$ that goes $v_2\to v$

Of these three paths, two must have a length of the same parity, and together form an even loop.