Euler & Hamiltonian Paths

In the 1700s the city of Königsberg had seven bridges, and its citizens wondered: could you stroll through town crossing every bridge exactly once and return home? Leonhard Euler proved it was impossible — and in doing so invented graph theory itself. He turned the city into a graph and discovered that whether such a walk exists depends on one simple count: how many vertices have an odd degree.