📂Graph Theory

Fleury's Algorithm Proof

Definition ¹

Let $G$ be an Euler graph. Then, an Euler trail can be made in the following way.

Start from an arbitrary vertex $u$ and follow these two rules to make the trail:

• (i): Already passed edges are removed. If removing an edge results in an isolated vertex, that vertex is also removed.
• (ii): At each step, bridges are only crossed if there are no other alternatives.

---

• If removing an edge $b \in G$ results in the graph being disconnected, then $b$ is called a bridge.

Explanation

The existence of an Euler trail in an Euler graph is guaranteed by its definition, but it does not specify what the Euler trail looks like. The Fleury’s algorithm provides a way to construct an Euler trail from a given Euler graph.

Proof

Euler graph equivalence condition: Let $G$ be a connected graph.

It is equivalent to say that $G$ is an Euler graph and all vertices of $G$ have an even degree.

If the trail goes out from $u$ and enters vertex $v$, that edge is removed. If $v = u$, then loop until $v \ne u$. If $v \ne u$, then the removed subgraph $H$ is still a connected graph, and only the vertices $u$ and $v$ have odd degrees. Therefore, it must be shown that upon repeating this removal, $H$ is still a connected graph. If it were assumed that for some vertex $w$, $H - vw$ is not a connected graph, it would mean that there exists some component $K$ that includes $w$ but not $u$. Since the vertex $w$ in $K$ has an odd degree, $K$ must have another vertex with an odd degree. However, this is a contradiction, so we can guarantee that $H - vw$ is a connected graph. In other words, no matter how many times this removal is repeated, it remains a connected graph. According to rule (ii), at any step, a bridge can only be removed at the end, hence the end of the trail must be $u$.

■