Graphs, degrees, and Eulerian trails

Definition and scope FACT

A finite undirected multigraph $G=(V,E)$G=(V,E) consists of a finite set of vertices $V$V and a finite collection of edges $E$E. Each edge joins two vertices without imposing a direction of travel. Multiple edges may join the same pair of vertices; a loop may also join a vertex to itself. A simple graph is the special case with no loops or parallel edges.

This framework is chosen because several bridges in Königsberg connected the same land areas: representing them requires parallel edges. This article covers neither directed graphs, in which an edge has a direction, nor weighted graphs, in which an edge carries, for example, a distance or a cost.

The underlying multigraph therefore retains only the incidence relation: which vertices each edge joins. The drawn positions, lengths, and angles are not part of its definition. These data can be added to the model when useful, but they are not necessary for the problem studied here.

Essential vocabulary FACT

An Eulerian trail uses every edge exactly once. It is open if its endpoints differ and becomes an Eulerian circuit if it returns to its starting vertex. Here, the word “Eulerian” concerns edges, not vertices.

The handshaking lemma FACT

Every ordinary edge has two ends and adds 1 to the degree of each of its vertices. A loop also has two ends, both at the same vertex, and therefore adds 2 to its degree. Counting with multiplicity, every edge contributes exactly 2 to the total sum:

$\sum_{v\in V} \deg(v)=2\,|E|$v∈V∑​deg(v)=2∣E∣

The right-hand side is even. Even-degree vertices contribute an even sum; the sum of the odd degrees must therefore also be even. A sum of odd integers is even if and only if it contains an even number of terms. Consequently, there is always an even number of odd-degree vertices.

In a simple graph representing an assembly, an edge means that two people shook hands. The lemma then states that the number of people who took part in an odd number of handshakes is even. This image explains its name, but the proof also applies to multigraphs and loops under the preceding degree convention.

The bridges of Königsberg FACT

The historical problem describes four land areas connected by seven bridges. The question was to find a walk that crossed each bridge exactly once, without requiring a return to the starting point.

Euler designated the areas with letters and represented successive crossings as sequences of letters. In the modern graph-theoretic reformulation, each area becomes a vertex and each bridge an edge. The resulting multigraph has four vertices of degrees 5, 3, 3, and 3. Their sum is 14, which is twice the number of edges (seven), in accordance with the lemma.

In an Eulerian trail, all incident edges are used. Each passage through an intermediate vertex consumes them in pairs: one to enter and one to leave. Thus, only the start and end of an open Eulerian trail have odd degree, whereas an Eulerian circuit has none.

Königsberg has four. No trail that uses each of the seven bridges exactly once exists. Euler established this impossibility and formulated the general parity rules; the modern theorem gives the complete characterization.

The modern Eulerian theorem FACT

Consider a finite undirected multigraph in which all vertices of nonzero degree belong to the same connected component.

• It has an Eulerian circuit if and only if all its vertices have even degree.
• It has an open Eulerian trail if and only if exactly two vertices have odd degree; they are necessarily its start and end.

Necessity follows from entry–exit pairing. Sufficiency is constructive. When all degrees are even, start at a vertex incident to an edge and follow edges that have not yet been used. It is impossible to get stuck at another vertex: by parity, each arrival there leaves an unused edge by which to depart. The trail must therefore return to the starting point and form a circuit.

If edges remain, connectedness guarantees that a vertex on the circuit touches an unused part. Build a new circuit from that vertex, then splice it into the first. Repeating the operation yields a circuit containing all edges: this is the principle of Hierholzer’s algorithm.

If exactly two odd-degree vertices exist, temporarily add an edge between them. All degrees become even; construct an Eulerian circuit, then remove the added edge. The circuit then opens into a trail whose endpoints are precisely the two odd-degree vertices.

Modeling requires choosing the right structure FACT

Roads, software dependencies, molecules, and electrical circuits can all be represented by graphs, but not by the same model without qualification.

• A road network may be undirected or directed and often carries distances or travel times.
• A dependency graph is generally directed: a cycle in it expresses a circular dependency.
• A molecular graph carries labels on atoms and bonds.
• An electrical network adds physical quantities and laws that incidence alone does not contain.

The benefit of abstraction is therefore not that a single algorithm would work everywhere. It is that the common structure—vertices and edges—is separated from domain-specific information, after which a theorem or algorithm is chosen whose assumptions exactly match the graph that was built.

Summary

In a finite undirected multigraph whose edges belong to the same component, degree parity determines whether every edge can be traversed exactly once: zero odd-degree vertices for a circuit, exactly two for an open trail.

Main references FACT

• Leonhard Euler — Solution of a Problem in the Geometry of Position, English translation
• University of Warwick — Combinatorics, Handshaking Lemma and Euler Circuits
• Carnegie Mellon University — Eulerian Paths and Circuits