Up: Introduction to graphs
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.
The set of such digraphs is well-ordered under containment.
Assume proposition is false and let
be a minimal counterexample. Let
be a non-trivial closed path in
, for instance the longest closed path.
must be even, so
is even. Hence each connected
is Eulerian as
is minimal. But then
is Eulerian: you can walk along
and include all edges of connected
when encountered -- giving a contradiction.
Hence there are no minimal counterexamples.