1

I am trying to understand the proof of the Fleury algorithm for finding eulerian path, but to no avail. Okay, we assume the graph is Eulerian and then give the exact procedure on how to continue, but the first thing I don't understand is what exactly do we want to prove with respect to those two steps?

The only proof I have is from my textbook and I have appended it here.

Edit: I have added the proof from my textbook.It is a translation since it is not in english so correct me if I messed it up somewhere.

So it says: Let us show that the algorithm will not get stuck at any step. In other words, let us show that in every step we will be able to leave the vertex we are currently in. (Why do we show this?) Suppose that we started the algoritm in some vertex $u$ and came to some other vertex $v$. If $v\neq u$ , then the subgraph $H$ that remains after removing the edges is connected and there are only two vertices of odd degree in it, namely $v$ and $u$. (Now comes the step I really don't understand.) We have to show that removing any next edge will still leave $H$ connected, which is equivalent to showing that $v$ has only one outgoing bridge. (Huh, why?) Now, suppose $v$ has more than one outgoing bridge. and let's label one of them as s $vw$ for some $w$. If we remove $vw$, then the connected component that contains $w$ now has all vertices of even degree and only one of odd degree, namely $w$ since $u$ does not belong to that component which is a contradiction.

darxsys
  • 311

1 Answers1

4

I came across a similar proof in the textbook Introduction to Graph Theory by Robin J. Wilson. I also had a hard time understanding this proof.

  1. We have to show that removing any next edge will still leave H connected, which is equivalent to showing that v has only one outgoing bridge.

If v has more than one outgoing bridge, this means that traversing one of the bridge and erasing it would leave you with 2 disconnected components. This cannot be possible in an Eulerian graph, because after traversing all the edges in the disconnected component there is no way to come back to the other component.

  1. Now, suppose v has more than one outgoing bridge. and let's label one of them as vw for some w.

This is in order to prove a contradiction; assume that there is such an outgoing bridge vw.

  1. If we remove vw, then the connected component that contains w now has all vertices of even degree and only one of odd degree, namely w.

By definition, all nodes in in an Eulerian graph have even degree (this is proved earlier in the textbook). So removing the bridge leaves w with odd degree.

  1. since u does not belong to that component which is a contradiction.

u is not connected to w, otherwise vw is not a bridge. Also by the handshaking lemma (every finite undirected graph has an even number of vertices with odd degree), this means that there must another vertex in the component of w that also has an odd degree. Since this other vertex originally had odd degree (because we only removed vw), this is a contradiction as Eulerian graphs must have vertices of even degree.

Shunji Lin
  • 143