## The bridges of Königsberg (Graph Theory)

Euler made a crucial observation: if a path through this network is going to cross every link exactly once, then each node within the path must have an even number of links attached to it. That’s because whenever you enter the node by one link, you need to leave it by another, so the node needs two links if you visit it once, four if you visit it twice, and so on. The only nodes that can have an odd number of links attached to them are the nodes where the walk starts and ends (if they are distinct).

This immediately tells us that the path we are looking for doesn’t exist in the Königsberg problem. All nodes have an odd number of links attached to them. The beauty of this argument, as Euler suggested in his letter, is that it works for any network, no matter how large or complex. A path that crosses every link exactly once only exists if all, or all but two, nodes have an even number of links attached to them. The converse is also true (though Euler didn’t deliver a rigorous proof for this): if all, or all but two, nodes have an even number of links attached to them, then a path that crosses every link exactly once exists.

Euler’s thoughts about the Königsberg problem marked the beginning of an area of maths called graph theory, which you might also call network theory.