Graph with no odd degree vertex

Question

I'm studying graphs and i'm stuck with this doubt.

We have a connected graph with no odd degree vertex.

Why, formally, this graph must contain a cycle ???

Answer 1

Actually we also need the condition $\lvert G \rvert \geq 2$. Let $G$ be connected and $\lvert G \rvert \geq 2$. Suppose $G$ does not contain a cycle (i.e. $G$ is a tree). We show that $G$ must contain a vertex of odd degree, specifically degree 1.

Let $v_1, \ldots, v_k$ be a path of maximal length. Then $k \geq 2$ since $\lvert G \rvert \geq 2$. We will use the notation $\Gamma(v)$ for the neighbourhood of $v$. We have that $\Gamma(v_k) \subset \{v_1, \ldots, v_{k-1}\}$ else the path can be extended, contradicting maximality. In addition $v_1, \ldots, v_{k-2} \not \in \Gamma(v_k)$ else we can form a cycle. Therefore $\Gamma(v_k) = \{v_{k-1}\}$ exactly therefore $d(v_k) = 1$.

Therefore if $G$ has only vertices of even degree, there must be a cycle.

Answer 2

(Assume the graph has an edge.)

We find a longest path in the graph and call one of its endpoints $x$:

• If $x$ is not connected to anything else, then $x$ has degree $1$, contradicting the degree requirement.

• If $x$ is adjacent to a vertex outside the path, it's not a longest path, giving a contradiction.

• Thus $x$ is adjacent to another vertex in the path, giving a cycle.

(Also note that the claim is only true for finite graphs.)