Vertices and Edges: Mapping Connections with Graphs

In 1736, the people of Königsberg wondered whether a walker could cross all seven of their city's bridges exactly once without recrossing any. Mathematician Leonhard Euler solved the puzzle by turning the city into a simple picture made of dots and lines — and accidentally invented an entire branch of math called graph theory.

Define vertex and edge in your own words. Explain the story of the Seven Bridges of Königsberg. Calculate the degree of a vertex in a graph. Draw and analyze your own graph.

A graph in math has nothing to do with bar charts or line graphs you make in class. Instead, it's a picture made of two simple parts: vertices, which are just points or dots (sometimes called nodes), and edges, which are the lines that connect two vertices together. Picture your five closest friends as five dots on a page. If you draw a line between every pair of friends who know each other, you've just built a graph.

In the 1700s, the city of Königsberg (now Kaliningrad, Russia) had two islands connected to the mainland and to each other by seven bridges. Locals wondered: could you take a walk through the city and cross every single bridge exactly once, without recrossing any? Mathematician Leonhard Euler turned the city into a graph — each land area became a vertex, each bridge became an edge — and proved mathematically that it could not be done. His 1736 solution is considered the birth of graph theory.

Once you have a graph, one of the first things mathematicians measure is degree: how many edges touch a single vertex. In our Königsberg example, three of the four land areas had an odd degree (an odd number of bridges touching them). Euler proved that a path crossing every edge exactly once — now called an Euler path — can only exist if a graph has zero or exactly two vertices with an odd degree. Königsberg had four, so the walk was impossible.