Euler and Hamilton Paths

An Euler circuit is simply a route that travels every road (edge) exactly once and comes back home, like drawing a figure without lifting your pen or going over a line twice. It's named after Leonhard Euler, who solved the first problem of this kind, and it's good for planning any route that has to cover every street: snowplows, mail carriers, street sweepers. The rule looks formal, but it's only two checks: "connected" (you can get everywhere) and "$\deg(v)$ is even for every vertex" (every intersection has an even number of roads). If both hold, a circuit exists; if either fails, it doesn't. That's the whole test.

In 1736 Euler was asked whether you could walk through the city of Königsberg crossing each of its seven bridges exactly once. People had tried and failed, but nobody knew whether it was impossible. Euler's insight was that the shapes and distances don't matter at all, only what connects to what. Make each land mass a vertex and each bridge an edge, and the degrees are 5, 3, 3 and 3. That one move invented graph theory.

Why degrees decide. Follow an Euler circuit and watch any one vertex. Every time the route passes through, it comes in along one edge and leaves along another, so it uses up edges at that vertex in pairs. The start works the same way, since the circuit leaves it at the beginning and comes back at the end. So every degree has to be even. Euler showed the converse too: in a connected graph with all degrees even, you can always find such a circuit.

Euler paths don't have to return to the start, and that loosens things just enough. The start and end vertices are the only places where an edge isn't paired with another, so they're allowed to be odd. Euler paths exist exactly when there are 0 or 2 odd-degree vertices, and with 2, the path starts at one and ends at the other. Königsberg has 4 odd vertices, so no walk works.

Hamilton cycles visit every vertex once instead. They sound like the same kind of problem but are much harder: no efficient test is known, and finding the shortest one is the traveling salesman problem. A useful sufficient condition is Dirac's theorem: if every vertex of an $n$-vertex graph ($n \ge 3$) has degree at least $n/2$, a Hamilton cycle exists.

A common mistake. It's tempting to mix up the two: Euler is about edges (every road once), Hamilton is about vertices (every town once). And Dirac's theorem only works one way. A graph can fail it and still have a Hamilton cycle; the cycle $C_6$ has every degree 2, below $6/2 = 3$, and it is a Hamilton cycle.

Snowplows, street sweepers and mail carriers plan Euler-style routes that cover every street; delivery companies face the much harder Hamilton-style traveling salesman problem.