Our editors will review what you’ve submitted and determine whether to revise the article.
Join Britannica's Publishing Partner Program and our community of experts to gain a global audience for your work! The Königsberg bridge problem was an old puzzle concerning the possibility of finding a path over every one of seven bridges that span a forked river flowing past an island—but without crossing any bridge twice. His proof involved only references to the physical arrangement of the bridges, but essentially he proved the first theorem in graph theory.degree, which is defined as the number of edges that enter or exit from it.
The vertices and edges of a polyhedron form a graph on its surface, and this notion led to consideration of graphs on other surfaces such as a torus (the surface of a solid doughnut) and how they divide the surface into disklike faces.
Euler’s formula was soon generalized to surfaces as Euler characteristic).
If there is a path linking any two vertices in a graph, that graph is said to be connected.
A path that begins and ends at the same vertex without traversing any edge more than once is called a A graph is a collection of vertices, or nodes, and edges between some or all of the vertices.
Nonplanar graphs cannot be drawn on a plane or on the surface of a sphere without edges intersecting each other between the vertices.
The use of diagrams of dots and lines to represent graphs actually grew out of 19th-century chemistry, where lettered vertices denoted individual atoms and connecting lines denoted chemical bonds (with degree corresponding to valence), in which planarity had important chemical consequences.
Asked originally in the 1850s by Francis Guthrie, then a student at University College London, this problem has a rich history filled with incorrect attempts at its solution.
In an equivalent graph-theoretic form, one may translate this problem to ask whether the vertices of a planar graph can always be coloured by using just four colours in such a way that vertices joined by an edge have different colours.