Eulerian and Hamiltonian Graphs

In the old Prussian city of Königsberg, the river Pregel split the town into four pieces — two banks and two islands — stitched together by seven bridges. On idle Sunday afternoons the townsfolk played a game: could you stroll through the city, crossing every bridge exactly once, and come home again? Nobody ever managed it, but nobody could say why.

In 1736 Leonhard Euler proved it was impossible — and in doing so he threw away the map. Distances, shapes, the curve of the river: none of it mattered. All that mattered was what connects to what. That single move — replacing land with dots and bridges with lines — invented an entire branch of mathematics: graph theory. This page is about the question Euler answered, and the surprisingly deep line it draws through mathematics.

Königsberg as a graph

Shrink each landmass to a single vertex (a dot) and draw one edge for each bridge. Because two pairs of landmasses are joined by two bridges each, this is a multigraph — parallel edges are allowed. Step through to read off the degree of each vertex (how many edges meet it).

Every one of the four vertices has odd degree. Hold that thought — it is exactly the fact that dooms the Sunday stroll.

Trails and circuits that use every edge

A walk that uses every edge of a connected graph exactly once has a name:

an Eulerian trail — travels every edge once (start and end may differ);
an Eulerian circuit — an Eulerian trail that also returns to its start (a closed loop).

The townsfolk wanted an Eulerian circuit (leave home, cross all seven bridges, come home). Euler found a test so simple it fits on a fingernail — you only ever look at the degrees.

In a connected graph:

an Eulerian circuit exists \iff every vertex has even degree;
an Eulerian trail (open) exists \iff exactly 0 or 2 vertices have odd degree.

Königsberg has four odd-degree vertices — more than the two an open trail can tolerate, and far from the zero a circuit demands. So no such walk exists. Not "nobody has found one yet": none can exist. Case closed, forever.

Why the degrees decide everything

The reason is beautifully simple. Think about any vertex that is not where you start or finish. Every time your walk passes through it, you arrive on one edge and leave on another — you spend edges in pairs. Pass through it three times and you have used 6 edges; the vertex must have even degree, or you would eventually arrive with no fresh edge to leave by and get stuck.

The only vertices allowed to be odd are the two ends of an open trail: the start (which you leave without first arriving) and the finish (which you arrive at without leaving). If the walk is a circuit, start and finish are the same vertex, so every vertex — including that one — must be even. That is the whole proof of the "only if" direction, in one paragraph.

Now watch one that works

Here is the famous "envelope" — the puzzle of drawing it without lifting your pen or retracing a line. Its two bottom corners A and B have degree 3 (odd); everything else is even. Exactly two odd vertices, so Euler promises an open trail — and it must start at one odd corner and end at the other. Step through to trace it.

Try starting anywhere else and you will always strand yourself. The two odd vertices are not optional decorations — they are the forced start and finish line.

A different question entirely: Hamiltonian graphs

Swap one word and the whole world changes. Instead of using every edge once, ask for a walk that visits every vertex once:

a Hamiltonian path — visits every vertex exactly once;
a Hamiltonian cycle — a Hamiltonian path that returns to its start.

It sounds like a cousin of Euler's problem, but it is a monster in disguise. There is no easy degree test. In fact, deciding whether a large graph has a Hamiltonian cycle is NP-complete — one of the genuinely hard problems of computer science, with no known shortcut faster than, in the worst case, checking a colossal number of routes. Euler's question you answer at a glance; Hamilton's can defeat a supercomputer.

There are helpful sufficient conditions — if a graph is "dense enough" it must be Hamiltonian:

For a simple graph on n \ge 3 vertices:

Dirac: if every vertex has degree \ge \tfrac{n}{2}, the graph has a Hamiltonian cycle;
Ore: if every pair of non-adjacent vertices has degree-sum \ge n, the graph has a Hamiltonian cycle.

But read the arrow carefully: these are sufficient, not necessary. A sparse graph — a plain cycle, where every vertex has degree only 2 — is Hamiltonian yet fails Dirac's condition completely. Passing the test guarantees a Hamiltonian cycle; failing it guarantees nothing at all.

The Euler test, in one line of code

Because it only reads degrees, Euler's circuit test is trivial to program — this is the entire algorithm for a connected graph:

function hasEulerianCircuit(degrees: number[]): boolean { // assumes the graph is connected // true iff EVERY vertex has even degree return degrees.every((d) => d % 2 === 0); } function hasEulerianTrail(degrees: number[]): boolean { const odd = degrees.filter((d) => d % 2 !== 0).length; return odd === 0 || odd === 2; } // Königsberg: degrees 3, 3, 5, 3 — four odd vertices console.log(hasEulerianCircuit([3, 3, 5, 3])); // false console.log(hasEulerianTrail([3, 3, 5, 3])); // false

There is no such tidy function for Hamiltonicity — and, as far as anyone knows, there cannot be a fast one. That gulf between two nearly identical-sounding questions is one of the deepest surprises in all of mathematics.

Euler's leap was to notice that the shape of Königsberg was irrelevant. Stretch the river, bend the bridges, move the islands — as long as the same lands stay joined by the same bridges, the answer never changes. He was studying a property that survives any stretching or squashing, only tearing and gluing matter. He even called it geometria situs, "the geometry of position."

That idea — geometry without measurement, where a coffee mug and a doughnut are "the same" because each has one hole — grew into topology, now one of the great pillars of modern mathematics. A game about a Sunday walk quietly opened two entire fields: graph theory and topology. Not bad for an afternoon's puzzle.

The single most common mix-up: Eulerian is about EDGES; Hamiltonian is about VERTICES. An Eulerian trail uses every edge once (it may revisit vertices as often as it likes); a Hamiltonian path visits every vertex once (it may skip edges entirely). Say it out loud before you start a problem — edges or vertices? — because the two questions have wildly different difficulty.

And mind the two versions of Euler's test. "Every vertex even" is the rule for a closed circuit. For an open trail the rule loosens to "exactly 0 or 2 odd vertices." Königsberg has four odd vertices, so it fails both — there is no circuit and not even an open crossing of all seven bridges.