# On the proof of Fleury's algorithm. (Question 3)

On pages 42-43 in [1], it says:

We conclude our introduction to Eulerian graphs with an algorithm for constructing an Eulerian trail in a give Eulerian graph. The method is know as Fleury's algorithm.

THEOREM 2.12 Let $G$ be an Eulerian graph. Then the following construction is always possible, and produces an Eulerian trail of $G$.

Start at any vertex $u$ and traverse the edges in an arbitrary manner, subject only to the following rules:

(i) erase the edges as they are traversed, and if any isolated vertices result, erase them too;

(ii) at each stage, use a bridge only if there is no alternative.

Proof. We show first that the construction can be carried out at each stage.

Suppose that we have just reached a vertex $v$, erasing the edges as we go. If $v \neq u$, then the subgraph $H$ that remains is connected and has only two vertices of odd degrees, $u$ and $v$. To show that the construction can be carried out, we must show that the removal of the next edge does not disconnect $H$ $-$ or, equivalently, that $v$ is incident with at most one bridge. But if this is not the case, then there exists a bridge $vw$ such that the component $K$ of $H-vw$ containing $w$ does not contain $u$ (see the figure below). Since the vertex $w$ has odd degree in $K$, some other vertex of $K$ must also have odd degree, giving the required contradiction.

Please look at the last sentence of the proof. Why does some other vertex of $K$ must also have odd degree? Thanks in advance.

[1] Robin J. Wilson, Introduction to Graph Theory, 5th ed., Prentice Hall, 2012.

From earlier, you know that all the vertices in $H$ except $u$ and $v$ have even degree. Meaning in particular that every vertex in $K$ has even degree. Once you visit $w$, $K$ becomes a component of $H$ with exactly one odd vertex, $w$. But it is impossible to have a graph with exactly one odd vertex, since sum of degrees of all the vertices equals $2 \times \text{number of edges}$, which is an even number.