2
$\begingroup$

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:

  1. Use induction on $ e(G) $. Done if $ e(G) = 0 $.
  2. 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.
  3. 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 $.
  4. 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.

1 Answers 1

1

As you noted, all vertices in the circuit $C$ have even degree. Thus, you are taking the degrees of $G$ (all of which are even) and decreasing them all by an even number (possibly 0) by removing the edges of $C$. The result is that every vertex in $G - E(C)$ has even degree ("even minus even is even"). That's all there is to it.

  • 0
    Thank you, I understand fully.2011-07-20