Graph Theory and the Seven Bridges of Königsberg: A Problem That Built a New Branch of Math

Introduction

On any given Sunday in the early eighteenth century, the citizens of Königsberg — a prosperous city in what was then Prussia, now the Russian city of Kaliningrad — would stroll along the banks of the River Pregel and across its seven bridges. The river divided the city into four distinct land masses: two riverbanks, a large island called Kneiphof in the middle of the river, and a second smaller island where the two branches of the river met.

At some point — nobody knows exactly when — a question began circulating among the citizens as a kind of recreational puzzle: Is it possible to take a walk through the city, crossing each of the seven bridges exactly once?

It sounds like a simple question. People tried it on foot, drew maps, traced routes with their fingers. Nobody could find a route that worked — but nobody could prove that no such route existed either. The puzzle nagged at people for years.

In 1736, it reached the desk of Leonhard Euler — the same Swiss mathematical giant we met in our article on Euler's Identity. His solution to the Königsberg bridge problem did not just answer the puzzle. It invented an entirely new branch of mathematics: graph theory. And graph theory turned out to be one of the most powerful and widely applied mathematical tools in human history.

The City of Königsberg and Its Seven Bridges

To understand the problem, it helps to picture the geography clearly.

The River Pregel flowed through Königsberg in two branches, creating four separate land areas:

Region A: The northern bank of the river.
Region B: The southern bank of the river.
Region C: Kneiphof Island, the large central island.
Region D: The eastern area where the two river branches met.

Seven bridges connected these regions:

Two bridges connected the northern bank (A) to Kneiphof Island (C).
Two bridges connected the southern bank (B) to Kneiphof Island (C).
One bridge connected the northern bank (A) to the eastern area (D).
One bridge connected the southern bank (B) to the eastern area (D).
One bridge connected Kneiphof Island (C) to the eastern area (D).

The challenge: start anywhere, walk across each of these seven bridges exactly once, and return to — or simply arrive at — any land area. No bridge may be crossed twice. No bridge may be skipped.

Simple enough to state. Impossible to solve — but not for the reason most people assumed.

Euler's Revolutionary Insight

When Euler encountered the problem, he recognised immediately that it was unlike the geometry problems of his era. It was not asking about lengths, angles, or areas. It did not matter how long the bridges were, how wide the river was, or how far apart the land masses lay. The only thing that mattered was the pattern of connections between the land areas.

This was a profound conceptual shift. Euler was moving away from the geometry of measurement — of distances and shapes — toward a new kind of mathematics concerned only with relationships and connectivity. He was, without yet having the word for it, inventing topology and graph theory simultaneously.

Abstracting the Problem

Euler's first move was to simplify the problem radically. He replaced each land area with a single point — what we now call a vertex (or node). He replaced each bridge with a line connecting two points — what we now call an edge. The result was a simple diagram: four points connected by seven lines.

This diagram — a collection of vertices connected by edges — is what mathematicians today call a graph. Euler had just drawn the first graph in history.

The question about crossing all seven bridges exactly once became a question about whether it was possible to trace all seven edges of the graph in a single continuous path, traversing each edge exactly once. Such a path is now called an Eulerian path in Euler's honour.

The Key Observation: Degrees of Vertices

Euler then made the observation that cracked the problem open. He thought carefully about what must happen at each vertex as you travel along an Eulerian path.

Consider any vertex that is not your starting point or ending point. Every time your path passes through that vertex, it must arrive via one edge and depart via a different edge. Each visit therefore uses up two edges — one to enter, one to exit. So for any middle vertex, the number of edges connected to it must be even.

Now consider the starting vertex. Your path departs from it without arriving first, then may return and depart again (each such intermediate visit using two edges), and eventually either the path ends at a different vertex or returns to the start. If the path ends at a different vertex, the starting vertex contributes one unpaired departure — giving it an odd number of edges. Similarly, the ending vertex (if different from the start) contributes one unpaired arrival — also an odd number of edges.

Euler's conclusion:

If an Eulerian path exists that starts and ends at different vertices, exactly two vertices must have an odd number of edges (the start and the end). All others must have an even number.
If an Eulerian path exists that starts and ends at the same vertex — called an Eulerian circuit — then all vertices must have an even number of edges.
If more than two vertices have an odd number of edges, no Eulerian path exists.

The number of edges connected to a vertex is called its degree. Euler had discovered that the existence of an Eulerian path depends entirely on the degrees of the vertices.

Applying the Rule to Königsberg

Now Euler counted the degrees of the four vertices in the Königsberg graph:

Region A (northern bank): connected by 3 bridges — degree 3 (odd).
Region B (southern bank): connected by 3 bridges — degree 3 (odd).
Region C (Kneiphof Island): connected by 5 bridges — degree 5 (odd).
Region D (eastern area): connected by 3 bridges — degree 3 (odd).

All four vertices have odd degree. Since more than two vertices have odd degree, Euler's theorem tells us immediately and with absolute certainty:

No Eulerian path exists. It is impossible to cross all seven bridges of Königsberg exactly once.

The citizens of Königsberg had not been failing due to lack of creativity or persistence. The walk they were attempting was mathematically impossible — and Euler had proved it with elegant, irrefutable logic.

What Is Graph Theory?

The 1736 paper in which Euler solved the Königsberg bridge problem is considered the founding document of graph theory. But what exactly is graph theory, and what does it study?

Graph theory is the mathematical study of graphs — structures consisting of vertices (points) connected by edges (lines). A graph makes no assumptions about geometry: the vertices can be anywhere, the edges can be any length or shape, and only the pattern of connections matters.

Types of Graphs

Undirected graphs: Edges have no direction — if A is connected to B, then B is connected to A. A map of cities connected by roads is an undirected graph.
Directed graphs (digraphs): Edges have a direction — a connection from A to B does not imply a connection from B to A. A map of one-way streets is a directed graph.
Weighted graphs: Edges have numerical values — distances, costs, capacities, or travel times. A road map with distances is a weighted graph.
Connected graphs: Every vertex can be reached from every other vertex by following edges. A disconnected graph has isolated components.
Complete graphs: Every pair of vertices is connected by an edge. A complete graph with n vertices has n(n−1)/2 edges.
Bipartite graphs: Vertices can be divided into two groups such that every edge connects a vertex in one group to a vertex in the other. Job-matching problems are naturally modelled as bipartite graphs.
Trees: Connected graphs with no cycles — no closed loops. Family trees, computer file systems, and organisational charts are all trees.
Planar graphs: Graphs that can be drawn on a flat surface without any edges crossing.

Key Concepts in Graph Theory

Path: A sequence of vertices connected by edges, with no vertex repeated.
Cycle: A path that begins and ends at the same vertex.
Degree: The number of edges connected to a vertex.
Adjacency: Two vertices are adjacent if they are directly connected by an edge.
Connectivity: Whether it is possible to travel between any two vertices by following edges.
Subgraph: A graph formed from a subset of the vertices and edges of a larger graph.
Spanning tree: A subgraph that connects all vertices with the minimum number of edges and no cycles.

Graph Theory in the Modern World

When Euler solved the Königsberg bridge problem, he could not have imagined the world his new mathematics would help build. Graph theory is now one of the most practically important branches of mathematics, underlying technologies that billions of people use every day.

The Internet

The internet is, at its core, a graph. Every device — computer, phone, server, router — is a vertex. Every connection between devices is an edge. The engineers who design internet infrastructure use graph theory to ensure that data can travel efficiently from any point to any other, that the network remains connected even if individual links fail, and that bottlenecks are identified and eliminated.

The routing protocols that determine how data packets travel across the internet — choosing the fastest or most reliable path from source to destination — are graph algorithms. Every time you load a webpage or send a message, graph theory is at work routing your data.

Social Networks

Facebook, Instagram, Twitter, LinkedIn, and every other social network is a graph. Users are vertices. Friendships, follows, and connections are edges. Graph theory allows social networks to:

Suggest friends you might know by finding vertices two steps away from you.
Identify communities and clusters of tightly connected users.
Detect influential nodes — people whose connections make them central to the spread of information.
Analyse how information, rumours, or diseases spread through the network.
Detect fake accounts and bot networks by identifying anomalous graph structures.

GPS and Navigation

Every road map used by GPS navigation systems is a weighted graph. Intersections are vertices. Roads are edges. The weights on edges represent distances, travel times, or current traffic conditions.

When your phone calculates the fastest route from where you are to where you want to go, it is solving a shortest path problem on a weighted graph. The algorithm most commonly used — Dijkstra's algorithm, developed in 1956 — is a graph theory algorithm. Every navigation app in the world, from Google Maps to Apple Maps to ride-hailing services, runs on this foundation.

Search Engines

The World Wide Web is a directed graph: webpages are vertices, and hyperlinks are directed edges pointing from one page to another. Google's original breakthrough — the PageRank algorithm developed by Larry Page and Sergey Brin — was a graph theory algorithm that ranked the importance of a webpage by analysing the structure of links pointing to it.

The insight was simple and powerful: a webpage that many other important pages link to is probably important itself. PageRank calculated this importance by analysing the global structure of the web graph. It transformed search and created one of the most valuable companies in history — built on graph theory.

Airline Networks and Logistics

Airlines model their route networks as graphs: airports are vertices, routes are weighted edges. Graph theory helps airlines optimise their networks, minimise costs, schedule crews efficiently, and ensure that passengers can reach any destination with the fewest connections.

The same mathematics applies to courier and logistics companies. When a delivery company plans routes for its drivers, it is solving a variant of a famous graph theory problem called the Travelling Salesman Problem: find the shortest route that visits every required location exactly once and returns to the start.

Computer Science and Programming

Graphs appear throughout computer science:

Compilers use directed graphs to model dependencies between operations and optimise the order in which instructions are executed.
Database systems use graphs to model relationships between data and optimise query performance.
Artificial intelligence uses graph search algorithms to explore possible states in games, planning problems, and decision trees.
Computer networks are designed and analysed using graph theory to ensure reliability and efficiency.
Version control systems like Git model the history of a codebase as a directed acyclic graph.

Biology and Medicine

Graph theory has found remarkable applications in the biological sciences:

Protein interaction networks: Proteins in a cell interact with each other in complex networks modelled as graphs. Understanding the structure of these networks helps researchers identify drug targets and understand disease.
Neural networks: The brain itself is a graph of billions of neurons connected by trillions of synapses. Neuroscientists use graph theory to analyse brain connectivity and understand how neural structure relates to function.
Epidemiology: The spread of infectious diseases through populations is modelled as a process on a contact graph, where individuals are vertices and contacts between them are edges. During the COVID-19 pandemic, graph models helped predict how the virus would spread and evaluate the impact of different interventions.
Evolutionary trees: The evolutionary relationships between species are represented as trees — a special type of graph — called phylogenetic trees.

Chemistry

Molecules are graphs: atoms are vertices and chemical bonds are edges. Graph theory allows chemists to classify molecules, predict their properties, and search databases of known compounds for molecules with desired characteristics. The field of chemical graph theory uses graph invariants — properties of a graph that do not change when the graph is redrawn — to create numerical fingerprints for molecules used in drug discovery.

Famous Problems in Graph Theory

The Four Colour Theorem

If you want to colour a map so that no two adjacent regions share the same colour, how many colours do you need? The answer — always at most four — was conjectured in 1852 and not proved until 1976, when mathematicians Kenneth Appel and Wolfgang Haken used a computer to verify over 1,900 cases. It was one of the first major theorems proved with computer assistance, and its proof remains controversial among mathematicians who prefer human-readable proofs.

The Travelling Salesman Problem

A salesman must visit a set of cities, each exactly once, and return to his starting city. What is the shortest possible route? This problem is easy to state but extraordinarily hard to solve for large numbers of cities. It belongs to a class of problems called NP-hard — no efficient algorithm for finding the exact solution is known, and most computer scientists believe none exists. Finding good approximate solutions to the Travelling Salesman Problem has enormous practical importance in logistics, manufacturing, and circuit board design.

The Minimum Spanning Tree

Given a connected weighted graph, find the subgraph that connects all vertices with the minimum total edge weight and no cycles. This is the minimum spanning tree problem, and efficient algorithms for solving it exist. It is used in network design — finding the cheapest way to connect all nodes in a network — and in clustering algorithms in machine learning.

The P vs NP Problem

One of the seven Millennium Prize Problems — each carrying a one-million-dollar prize for a solution — is a question in graph theory and computational complexity: is every problem whose solution can be quickly verified also quickly solvable? If P = NP, many currently intractable problems would become efficiently solvable. If P ≠ NP, as most computer scientists believe, it would explain why certain problems are fundamentally hard. The answer, either way, would revolutionise mathematics and computer science.

Euler's Theorem and Related Results

Euler's Handshaking Lemma

One of the most elegant results in graph theory follows directly from Euler's work. In any graph, the sum of the degrees of all vertices equals twice the number of edges:

Σ deg(v) = 2|E|

This is because every edge contributes exactly 1 to the degree of each of its two endpoints — so counting all degrees counts every edge twice. A charming consequence: in any graph, the number of vertices with odd degree must be even. You can never have an odd number of odd-degree vertices — which is why the Königsberg problem, with four odd-degree vertices, was doomed from the start.

Euler's Formula for Planar Graphs

For any connected planar graph — one that can be drawn without edges crossing — Euler discovered a remarkable relationship between the number of vertices (V), edges (E), and faces (F, including the outer infinite face):

V − E + F = 2

This formula, known as Euler's Formula for planar graphs, is one of the foundational results of topology. It applies to any convex polyhedron as well — a cube has 8 vertices, 12 edges, and 6 faces: 8 − 12 + 6 = 2. A tetrahedron has 4 vertices, 6 edges, and 4 faces: 4 − 6 + 4 = 2. The formula always holds.

Graph Theory and WAEC/JAMB Mathematics

Graph theory as a formal topic is not yet in the standard WAEC or JAMB syllabus, but its foundational ideas connect directly to content you will study:

Network diagrams: Some WAEC Further Mathematics questions involve network problems that are graph theory applications in disguise.
Counting and combinatorics: The number of edges in a complete graph, the number of paths between vertices, and related counting problems connect to permutations and combinations in your syllabus.
Matrices: Graphs can be represented as matrices — the adjacency matrix has a 1 in row i, column j if vertex i is connected to vertex j, and 0 otherwise. Matrix algebra is directly examined in Further Mathematics.
Logical reasoning: Euler's approach to the Königsberg problem — abstracting a real-world situation into a mathematical model and then proving a general theorem — is exactly the kind of mathematical thinking that examination questions reward.
Sequences and series: Many graph theory results involve summing degrees or counting paths, connecting to series and summation notation.

Common Misconceptions About Graph Theory

"A graph is a chart or diagram with axes." In everyday language, "graph" often means a bar chart or line graph. In mathematics, a graph is a collection of vertices and edges — a completely different object. Context always clarifies which meaning is intended.
"Graph theory is only theoretical." As this article has shown, graph theory is one of the most practically applied areas of mathematics. It powers the internet, social networks, GPS, and search engines.
"Euler solved the Königsberg problem by finding a route." Euler did the opposite — he proved that no route exists. The power of his solution was not finding an answer but proving the impossibility of one.
"Graph theory is a recent invention." Graph theory began in 1736 — nearly three centuries ago — though its explosive growth in applications came with the rise of computers and networks in the twentieth century.

Conclusion

A Sunday afternoon puzzle about bridges in a Prussian city. A mathematician who looked at it and saw not a geography problem but a question about connections and relationships. A simple diagram of four dots and seven lines. A theorem about the degrees of vertices.

From these humble beginnings grew one of the most powerful and widely applied branches of mathematics in existence. Graph theory does not just describe the world — in a very real sense, it runs the world. The internet you browse, the social networks you use, the navigation apps that guide your journeys, the search engines that answer your questions, the algorithms that recommend your music — all are built on the mathematical foundations that Euler laid in 1736 when he asked a simple question about seven bridges.

Mathematics has a habit of doing this: a problem that seems trivial or merely recreational turns out, centuries later, to be the seed of something vast and indispensable. The citizens of Königsberg could not cross all seven bridges — but their failure to do so changed the world.