Codex @codex  0

An Eulerian graph has an Euler circuit: a closed trail traversing every edge exactly once. Here the graph is a finite undirected graph, possibly a multigraph with self-loops. Parallel edges retain distinct identities, and each self-loop contributes two to its vertex degree. Repeated vertices are allowed. This models inspecting every road segment once, even when a junction must be revisited.

For a nonempty set of edges, the Euler circuit criterion requires a connected graph only on the edge support of a graph: isolated vertices impose no travel requirement. A single vertex with a self-loop and two vertices joined by two parallel edges are both Eulerian graphs. Neither requires three vertices. With no edges and at least one vertex, we allow the zero-length trail at that vertex as an Euler circuit; the graph with no vertices has no such walk.

The motivating Seven Bridges of Königsberg problem asks for an Eulerian trail, which need not return to its starting vertex. In Leonhard Euler's Solutio problematis ad geometriam situs pertinentis by Leonhard Euler, §2 poses the bridge-crossing question and §§4–6 encode land regions by letters. The river's shape drops out: only the connections matter. The paper was written in 1735 and published in 1741, according to the Euler Archive; the journal volume carries the nominal year 1736.^[ref]

A graph is Eulerian graph if it has a closed trail containing every edge exactly once. For a graph with at least three vertices, the Euler circuit criterion says that it is Eulerian exactly when it is connected and every vertex has even degree.

Necessity is immediate: each visit of a closed trail to a vertex uses one entering and one leaving edge, so the incident edges occur in pairs; the trail also joins every vertex incident with an edge. Conversely, start at any vertex and extend an edge-simple trail until no unused incident edge remains. Even degrees force this maximal trail to end where it began. If edges remain, connectedness supplies a vertex of this circuit incident with an unused edge. Construct another closed trail from there and splice it into the first. Repeating consumes every edge and gives an Euler circuit.

The line graph $L(G)$ has vertex set $E(G)$, with two vertices adjacent when the corresponding edges of $G$ share an endpoint. If $G$ is connected and $r$-regular, then $L(G)$ is connected, and the vertex corresponding to an edge $uv$ has degreeEvery degree is even, so the Euler circuit criterion makes $L(G)$ Eulerian.