next up previous contents
Next: Bibliography Up: Introduction to graphs Previous: Multigraphs   Contents

Eulerian Digraphs

A digraph is Eulerian if there is a closed path covering all the edges. A necessary condition is: the graph is connected and even (each vertex has an equal number of ``in'' and ``out'' edges). This is in fact sufficient.

Proposition 9.4.1   The set of such digraphs is well-ordered under containment.

Proof. Assume proposition is false and let $ G$ be a minimal counterexample. Let $ T$ be a non-trivial closed path in $ G$, for instance the longest closed path. Now $ T$ must be even, so $ G \setminus T$ is even. Hence each connected component of $ G \setminus T$ is Eulerian as $ G$ is minimal. But then $ G$ is Eulerian: you can walk along $ T$ and include all edges of connected components of $ G \setminus T$ when encountered -- giving a contradiction. Hence there are no minimal counterexamples. $ \qedsymbol$

root 2002-06-10