Eulerian Graphs

An Eulerian graph is a connected graph in which every vertex is of even degree.

A property of Eulerian graphs is that they can be completely traversed, returning to the start point without following any edge more than once or lifting pen from paper.

Note that an Eulerian graph may not be simple – so that some of the above arcs cross each other.

An Eulerian graph may have no odd vertices.

Proof

Suppose Q is an odd vertex.

We can divide the arc connecting Q to the rest of the graphs into entry arcs to Q and exit arcs from Q, and match each entry arc with a unique and distinct exit arc, else some arc would be traversed twice.

Since Q is a vertex of odd degree, the must be an arc left over. If this is an entry arc, then there is no exit arc that would not be otherwise traversed since every entry arc is associated with an exit arc. If this is an exit arc, then there is no entry arc that would not be otherwise traversed since every exit arc is associated with an entry arc.

You have no rights to post comments