Euler Network Characterization¶

Proposition¶

A finite connected undirected network has an Euler tour if and only if every vertex has even degree. Such a network is called an Euler network.

Interpretation¶

The proposition replaces a search over all possible routes by a check done vertex by vertex: in a connected network, a closed route using every edge exactly once exists exactly when all degrees are even.

Two networks of five vertices: one with all degrees even, which has an Euler tour, and the same network with an extra edge from B to D, which makes B and D odd so that only an open trail exists.

In the left network the degrees are $4,2,2,2,2$ , all even, and an Euler tour exists. The right network adds the edge $B-D$ $D$ , which raises the degrees of $B$ and $D$ to $3$ . Now no Euler tour exists, but a route that starts at $B$ , ends at $D$ and uses every edge once still does.

Even degree is necessary because a closed route pairs every arrival at a vertex with a departure; at the starting vertex, the first departure pairs with the final arrival. So the route uses the edges at each vertex two at a time. Sufficiency is the harder direction, and the cycle-splicing construction of the Euler tour algorithm establishes it. Connectedness cannot be dropped: two separate triangles have all degrees equal to 2, yet no single route covers both.

With exactly two odd vertices, as on the right, a connected network still has an open route between them that uses every edge once; the Königsberg network, with four odd vertices, has neither kind of route. The Chinese postman problem makes odd degrees even by duplicating paths, after which the proposition applies.

Key Results¶

One odd-degree vertex is enough to rule out an Euler tour.
Connectedness of the edges is required to traverse all edges in one tour: if the edges lie in two or more separate parts, no single tour covers them all (isolated vertices do no harm).
Parallel copies introduced by the Chinese postman construction are counted as separate edges.

Examples¶

The seven-bridge network violates the even-degree condition.
Duplicating suitable paths between odd-degree vertices makes their endpoint degrees even.

Prerequisites¶

Sources¶

OR Modelling · Week 4

Last updated: 27 October 2026 11:52