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. enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.