Eulerian Graphs

An Eulerian graph is a connected graph in which each vertex has even order. This means that it is completely traversable without having to use any edge more than once. It is possible to follow an Eulerian cycle starting from any vertex, visiting every other vertex, using all arcs, and returning to the start point without ever repeating an edge. Each vertex will be visited a number of times equal to half its order.

Figure 1. An Eulerian graph with 6 vertices.
Figure 1. An Eulerian graph with 6 vertices.

Semi-Eulerian Graphs

A semi-Eulerian graph has two vertices of odd order. An Eulerian cycle is not possible, but it is semi-traversable. You can draw the graph starting at one of the vertices with odd order and ending at the other including all of the edges as you go round, without removing your pencil from the paper.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.