= Eulerian graph
{c}
{wiki}
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.<Euler Archive, E53: Solutio problematis ad geometriam situs pertinentis>{ref}
Back to article page
