Eulerian graphs and semi-Eulerian graphs, including Eulerian circuits and trails that use every edge exactly once, and the degree conditions: all vertices even for an Eulerian graph and exactly two odd vertices for a semi-Eulerian graph.
An Eulerian circuit is a special kind circuit that traverses every edge exactly once.
In other words, a walk is Eulerian if it starts and ends at the same vertex, uses every edge, but does not reuse any edge.
Eulerian circuit ✓
Not an Eulerian circuit ✗, because DB not traversed.
Not an Eulerian circuit ✗, because DA traversed twice.
Not an Eulerian circuit ✗, does not start and end at the same vertex (not a circuit)
An Eulerian trail is a special kind of trail that traverses every edge exactly once.
It differs from an Eulerian circuit by the fact that a circuit must start and end in the same place, while an Eulerian trail can start and end at different vertices. Every Eulerian circuit is an Eulerian trail, but not versa. The following graph shows an Eulerian trail which is not an Eulerian circuit:
If a graph contains an Eulerian circuit, we call it an Eulerian graph.
If a graph contains an Eulerian trail but not an Eulerian circuit, we call it semi-Eulerian.
A graph can be Eulerian, semi-Eulerian, or neither.
Eulerian graph
Semi-Eulerian graph
If a graph is Eulerian, it must be that every vertex in the graph has an even degree.
If a graph is semi-Eulerian, then exactly two vertices in the graph have odd degree and all the others have even degree.
This also works backwards: If every vertex in a graph has even degree, then we know it's Eulerian. And if only two vertices have odd degrees, then we know it's semi-Eulerian.
The Eulerian graph above has vertices with even degree:
A: 4
B: 2
C: 2
D: 2
E: 2
The semi-Eulerian graph above has exactly two vertices with odd degree:
A: 1
B: 2
C: 3
D: 2
E: 2
This is true because an Eulerian circuit must visit every vertex, and each time it visits a vertex, it must use one edge to enter the vertex and one edge to leave the vertex, which means that edges have to come in pairs at every vertex.
A semi-Eulerian graph has exactly two vertices of odd degree. Any Eulerian trail on this graph must start at one of the vertices with odd degree and end at the other odd-degree vertex.
This is true because every time a trail passes through a vertex, it uses one edge to enter and one edge to leave. So every visit uses a pair of edges. There are only two exceptions, the starting vertex which we can leave without entering and the ending vertex which we enter and then never leave. Since an Eulerian trail has to use every edge, the only way to use an "unpaired" edge is at the start or the end.
Because A and C are the vertices with odd degree, any Eulerian trail on the graph must start at either A or C and end at the other vertex with odd degree.
Nice work completing Eulerian trails, circuits and graphs, here's a quick recap of what we covered:
Exercises checked off
Eulerian graphs and semi-Eulerian graphs, including Eulerian circuits and trails that use every edge exactly once, and the degree conditions: all vertices even for an Eulerian graph and exactly two odd vertices for a semi-Eulerian graph.
An Eulerian circuit is a special kind circuit that traverses every edge exactly once.
In other words, a walk is Eulerian if it starts and ends at the same vertex, uses every edge, but does not reuse any edge.
Eulerian circuit ✓
Not an Eulerian circuit ✗, because DB not traversed.
Not an Eulerian circuit ✗, because DA traversed twice.
Not an Eulerian circuit ✗, does not start and end at the same vertex (not a circuit)
An Eulerian trail is a special kind of trail that traverses every edge exactly once.
It differs from an Eulerian circuit by the fact that a circuit must start and end in the same place, while an Eulerian trail can start and end at different vertices. Every Eulerian circuit is an Eulerian trail, but not versa. The following graph shows an Eulerian trail which is not an Eulerian circuit:
If a graph contains an Eulerian circuit, we call it an Eulerian graph.
If a graph contains an Eulerian trail but not an Eulerian circuit, we call it semi-Eulerian.
A graph can be Eulerian, semi-Eulerian, or neither.
Eulerian graph
Semi-Eulerian graph
If a graph is Eulerian, it must be that every vertex in the graph has an even degree.
If a graph is semi-Eulerian, then exactly two vertices in the graph have odd degree and all the others have even degree.
This also works backwards: If every vertex in a graph has even degree, then we know it's Eulerian. And if only two vertices have odd degrees, then we know it's semi-Eulerian.
The Eulerian graph above has vertices with even degree:
A: 4
B: 2
C: 2
D: 2
E: 2
The semi-Eulerian graph above has exactly two vertices with odd degree:
A: 1
B: 2
C: 3
D: 2
E: 2
This is true because an Eulerian circuit must visit every vertex, and each time it visits a vertex, it must use one edge to enter the vertex and one edge to leave the vertex, which means that edges have to come in pairs at every vertex.
A semi-Eulerian graph has exactly two vertices of odd degree. Any Eulerian trail on this graph must start at one of the vertices with odd degree and end at the other odd-degree vertex.
This is true because every time a trail passes through a vertex, it uses one edge to enter and one edge to leave. So every visit uses a pair of edges. There are only two exceptions, the starting vertex which we can leave without entering and the ending vertex which we enter and then never leave. Since an Eulerian trail has to use every edge, the only way to use an "unpaired" edge is at the start or the end.
Because A and C are the vertices with odd degree, any Eulerian trail on the graph must start at either A or C and end at the other vertex with odd degree.
Nice work completing Eulerian trails, circuits and graphs, here's a quick recap of what we covered:
Exercises checked off