Why do degrees matter?
The key to Eulerian graphs is the degree of each vertex. Recall that the degree of a vertex is the number of edges incident to it.
In an Eulerian traversal, every time we arrive at a vertex through one edge, we usually need another edge to leave it. This naturally creates pairs of used edges: one for entering, one for leaving.
Because of this pairing, most vertices in an Eulerian traversal must have an even degree. If a vertex has odd degree, one edge is left unpaired, which means that vertex can serve only as a special endpoint of the traversal.
This simple observation is enough to characterize when Eulerian paths and cycles exist. Instead of searching blindly through all routes, we can inspect the degrees first.
Eulerian cycle vs. Eulerian path
There are two closely related notions:
A graph has an Eulerian cycle if there exists a closed walk that uses every edge exactly once and returns to the starting vertex.
A graph has an Eulerian path if there exists a walk that uses every edge exactly once, but it may start and end at different vertices.
The structural difference is reflected directly in the parity of the degrees: a cycle has no special endpoints, while a path has exactly two endpoints.
Therefore, an Eulerian cycle requires all relevant vertices to have even degree, while an Eulerian path allows exactly two odd-degree vertices.
The characterization theorem
Let G be a connected graph, ignoring isolated vertices. Then:
Eulerian cycle: G has an Eulerian cycle if and only if every vertex has even degree.
Eulerian path: G has an Eulerian path if and only if exactly zero or two vertices have odd degree.
The case of zero odd vertices corresponds to an Eulerian cycle, because the walk can start and finish at the same vertex. The case of two odd vertices corresponds to an open Eulerian path, starting at one odd vertex and ending at the other.
If a graph has more than two odd-degree vertices, then no Eulerian traversal exists.
Why connectivity is required
Degree conditions alone are not enough. The graph must also be connected once isolated vertices are ignored.
The reason is simple: an Eulerian traversal must cover every edge in a single walk. If the graph has edges split across disconnected components, no single walk can reach them all.
Isolated vertices do not matter, because they contribute no edges to be traversed. Eulerian questions are about covering edges, not merely visiting vertices.
So the full condition is: correct degree parity + connectivity of the non-isolated part.
Examples
Consider three typical cases:
Case 1: every vertex has even degree. Then the graph admits an Eulerian cycle.
Case 2: exactly two vertices have odd degree. Then the graph admits an Eulerian path, but not an Eulerian cycle.
Case 3: four or more vertices have odd degree. Then no Eulerian path exists.
These cases can often be determined immediately by inspection, which makes Eulerian problems much more tractable than Hamiltonian ones.
Connection to Königsberg
In the Königsberg graph, more than two vertices have odd degree. Therefore, the graph cannot have an Eulerian path.
Euler did not need to test all possible walks. Once the degree pattern was known, the answer followed directly from the structure.
This was one of the first great examples in mathematics of replacing geometric intuition with structural reasoning.