I'm going through a proof of the following theorem:
A connected graph $ G$ is Eulerian iff $d(x)$ is even $ \forall x \in G $.
The proof of the harder direction is roughly as follows:
- Use induction on $ e(G) $. Done if $ e(G) = 0 $.
- Given connected $G$ with $ e(G) > 0 $ and the relevant condition on the degrees of the vertices, suppose $G$ not Eulerian and let $C$ be a largest circuit in $G$ with no edges repeated. Note that $ e(C) > 0 $ as $G$ is not a tree.
- Let $H$ be a component of $ G - E(C) $ with $e(H) > 0$. Then $H$ is connected and $ d_H(x) $ is even for all $ x \in H $.
- etc
My problem is understanding why $d_H(x)$ is even for all x.
My thoughts:
We start with a connected graph in which every vertex has even degree. We remove a circuit C (and I see that $d_C(x) $ is even for all $ x \in C$). We then take a component $H$ of the remaining graph $ G - E(C) $ that has an edge. Suppose $H$ had a vertex $y$ with odd degree (in $H$). Then if we add $C$ back in to the graph, we see that $y$ must be adjacent to an odd number of vertices in $C$. This means that each of these vertices in $C$ must be adjacent to an odd number of vertices in $ G - E(C) - y $.
I'm stuck at this point. Am I overcomplicating things? I feel like this is something that should be obvious.
Thanks in advance.