Graph theory and the bridges of Königsberg

Long ago there was a city called Königsberg, built where a river split around two islands. Seven bridges tied the two riverbanks and the two islands together. The people there had a favourite puzzle for a Sunday walk: could you cross all seven bridges, each one exactly once, and end up back where you started?

Everyone tried. Nobody managed it. But trying and failing is not the same as proving it cannot be done, and that is what a mathematician named Leonhard Euler did in 1736.

His clever move was to throw away the map. The shape of the islands did not matter, and neither did how long each bridge was. All that mattered was which pieces of land were joined to which. So he shrank each piece of land to a single dot and drew each bridge as a line between two dots. Suddenly the whole city was just four dots and seven lines.

Looking at it that way, Euler could count. At every dot except your start and finish, you need one bridge to walk in and a different one to walk out, so the bridges at that dot have to pair up evenly. In Königsberg they did not. That was enough to prove the walk was impossible. And by turning a map into dots and lines, he had invented graph theory, the maths now hiding inside every road map, every social network and the internet itself.

Strip a network down to its bones and you get a graph: a set of dots, called vertices or nodes, joined by lines, called edges. That is the whole idea. The picture can be redrawn any way you like, stretched or bent, and it stays the same graph, because only the connections count, not the shapes or distances.

Königsberg becomes four nodes (the two banks and the two islands) and seven edges (the bridges). Two of the bridges run between the same pair of land masses, and a graph is happy to have more than one edge between two nodes.

Now the key quantity. The degree of a node is how many edges meet there. Euler's insight was about what a full tour needs. Suppose you want a route that uses every edge exactly once and returns to its start; this is called an Eulerian circuit. Every time your walk passes through a node, it arrives on one edge and leaves on another, so it eats the edges at that node two at a time. For the walk to close up neatly, every node must therefore have an even degree.

Königsberg's degrees are 3, 3, 3 and 5. Every single node is odd, so no Eulerian circuit can exist, and neither can a route that merely crosses every bridge once without returning home. That weaker route, an Eulerian path, is possible in exactly one case: when 0 or 2 of the nodes are odd. Zero odd nodes gives a circuit; two odd nodes gives a path that must start at one odd node and finish at the other. Four odd nodes, as here, gives nothing.

That is why the widget above always leaves you stranded. Add one more bridge and two of the corners flip from odd to even, dropping the odd count to two, and a complete walk springs into existence, though it will not bring you back to your doorstep. The real lesson is the abstraction itself. The exact same counting argument works for a maze of corridors, a mail round, or the lines of a drawing you want to trace without lifting your pen.

The objects, made precise. A graph \(G = (V, E)\) is a set of vertices \(V\) and a set of edges \(E\), each edge an unordered pair of vertices; allow repeated pairs and you have a multigraph, which is what Königsberg needs. The degree \(\deg(v)\) counts the edges incident to \(v\). Summing degrees counts every edge from both ends, which gives the handshake lemma \(\sum_{v \in V} \deg(v) = 2\lvert E\rvert\). Since the total is even, the number of odd-degree vertices must be even. So odd vertices always come in pairs, which is exactly why you cannot fix Königsberg's four odd corners with a single well-placed bridge, and why 0 or 2 (never 1) odd vertices is the condition below.

Euler's theorem. For a connected graph, an Eulerian circuit exists if and only if every vertex has even degree, and an Eulerian path (not necessarily closed) exists if and only if exactly zero or two vertices are odd. Necessity is the pairing argument from Level 2. Sufficiency follows from the fact that an even-degree connected graph decomposes into edge-disjoint cycles which can be spliced together into one closed tour (Hierholzer's algorithm builds it in linear time). Königsberg has four odd vertices, so it fails both tests at once.

Eulerian is easy, Hamiltonian is hard. It is tempting to think the sister question is just as tame: instead of using every edge once, visit every vertex once (a Hamiltonian path or cycle). It is not. There is no known efficient degree-style test for it. Deciding whether a Hamiltonian cycle exists is NP-complete, and the optimisation cousin, the travelling salesman problem, is NP-hard. That cliff between "every edge once" and "every vertex once" is one of the sharpest illustrations of the P versus NP question.

Where the field went. Euler's other great graph result, his formula \(V - E + F = 2\) for a connected planar graph, seeds topology and underlies the four-colour theorem on map colouring. Weighted and directed graphs carry shortest-path algorithms such as Dijkstra's, which is what your phone runs to route you across a city. Spectral properties of the adjacency matrix drive PageRank and the analysis of social graphs. All of it descends from one refusal to be distracted by geometry: the move that mattered was turning a question about distances and shapes into a question about connections and counting.