Contributions of Leonhard Euler To Mathematics - Graph Theory and Topology

Graph Theory and Topology

In 1736 Euler solved, or rather proved unsolvable, a problem known as the seven bridges of Königsberg. The city of Königsberg, Kingdom of Prussia (now Kaliningrad, Russia) is set on the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges. The question is whether it is possible to walk with a route that crosses each bridge exactly once, and return to the starting point. Euler's solution of the Königsberg bridge problem is considered to be the first theorem of graph theory. In addition, his recognition that the key information was the number of bridges and the list of their endpoints (rather than their exact positions) presaged the development of topology.

Euler also made contributions to the understanding of planar graphs. He introduced a formula governing the relationship between the number of edges, vertices, and faces of a convex polyhedron. Given such a polyhedron, the alternating sum of vertices, edges and faces equals a constant: V-E+F=2. This constant, χ, is the Euler characteristic of the plane. The study and generalization of this equation, specially by Cauchy and Lhuillier, is at the origin of topology. Euler characteristic, which may be generalized to any topological space as the alternating sum of the Betti numbers, naturally arises from homology. In particular, it is equal to 2-2g for a closed oriented surface with genus g and to 2-k for a non-orientable surface with k crosscaps. This property led to the definition of rotation systems in topological graph theory.