Lesson 4

It is easy to derive criteria for paths and for undirected graphs. As before, we assume that there are no isolated vertices in the graph.

1. An undirected graph has an Eulerian cycle if and only if it is connected and all its vertex degrees are even.
2. An undirected graph has an Eulerian path if and only if it is connected and has at most two vertices of odd degree. (Thus, there may be two or none. If there are two, then every Eulerian path will start and end at these vertices.)
3. A directed graph has an Eulerian path if and only if it contains an Eulerian cycle or is weakly connected and all its vertices are balanced except for two: one has an out-degree one higher, and the other — an in-degree one higher.