Every large Indian city built along a river faces the same everyday question, answered a thousand times over by a thousand different commuters: how do you get from one bank to the other, and does the specific route matter? Kolkata sits on the Hooghly, and travelling between Howrah and the city means crossing one of several bridges, including the well-known Howrah Bridge. Each crossing drops you into a different part of town, and each is a slightly different walk. Now imagine someone sets herself an unusual morning challenge: cross every bridge over the river exactly once, and end up back where she started, without recrossing any bridge. Is a route like that always possible?
The answer turns out to depend on nothing about distance, traffic, or walking speed, only on how the bridges are arranged. Mathematicians solved a version of exactly this puzzle, for a real city, close to 300 years ago, and in doing so invented an entire branch of mathematics that now quietly runs underneath UPI fraud checks, IRCTC route planning, and the "People You May Know" list on every social media app you use.
The Seven Bridges of Königsberg
In the 18th century, the Prussian city of Königsberg (today called Kaliningrad, part of Russia) was built where the Pregel river splits and flows around a central island. Counting that island, a second smaller island downstream, and the two riverbanks, the city had four distinct landmasses, connected to one another by seven bridges. Local legend held that it was impossible to plan a walk crossing every bridge exactly once, but nobody could explain why, until the Swiss mathematician Leonhard Euler took up the question in 1736.
Euler's key move was to strip away everything about the city that didn't affect the puzzle. The exact shape of the island, the width of the river, the distance between bridges: none of it changes whether a cross-every-bridge-once walk exists. All that matters is which landmasses connect to which, and by how many bridges. So Euler represented each landmass as a single point, called a vertex (plural: vertices, also called a node), and each bridge as a line joining two points, called an edge. A collection of vertices and edges like this is called a graph. This sketch of Königsberg, drawn in 1736, is generally considered the first graph ever used to solve a real problem.
Label the four landmasses A (the central island), B (the north bank), C (the south bank), and D (the smaller eastern landmass). Historically, two bridges connected A and B, two connected A and C, one connected A and D, one connected B and D, and one connected C and D: seven bridges in total, with no bridge directly joining B and C. Written out as an adjacency matrix, where each entry counts the bridges directly connecting a pair of landmasses, the graph looks like this:
A B C D
A 0 2 2 1
B 2 0 0 1
C 2 0 0 1
D 1 1 1 0
Add up each row and you get the degree of that vertex, the number of bridges touching it: A has degree 5 (2+2+1), B has degree 3 (2+0+1), C has degree 3 (2+0+1), and D has degree 3 (1+1+1). Add all four degrees together, 5+3+3+3 = 14, and you get exactly twice the number of bridges (2 × 7 = 14). That is not a coincidence: every bridge has two ends, so it gets counted once in each of the two landmasses it touches. This always-true fact is called the handshaking lemma: in any graph, the sum of all vertex degrees equals twice the number of edges.
Euler then asked a sharper question: what property of the degrees decides whether a cross-every-bridge-once walk exists? His reasoning was about arriving and leaving. Every time a walk passes through a landmass without starting or ending there, it uses one bridge to arrive and a different bridge to leave: the bridges at that landmass get used up in matched pairs. That means every landmass merely passed through must have an even degree. Only the landmass where the walk starts and the one where it finishes are allowed an odd degree, and if it starts and ends in the same place, even that one needs to be even. Generalising this, Euler proved that a connected graph has a walk using every edge exactly once, called an Eulerian path, only if it has exactly zero or exactly two vertices of odd degree. With zero odd vertices, the walk can start and end at the same place, forming a loop called an Eulerian circuit. With more than two odd vertices, no such walk exists at all, no matter how cleverly it is planned.
Look back at Königsberg's degrees: 5, 3, 3, 3. All four are odd, which means four vertices of odd degree, not zero and not two. By Euler's theorem, no walk can cross every bridge exactly once, whether or not it needs to return to its starting point. The riddle was not unsolved because nobody was clever enough to find the route. It was mathematically impossible, and Euler proved it without ever needing to try a single walk through the actual city.
What Exactly Is a Graph?
Formally, a graph is a pair of sets, written G = (V, E): a set of vertices V and a set of edges E, where each edge connects two vertices. Königsberg's bridges happened to form what is called an undirected graph: each edge is a two-way connection with no inherent direction, since walking across a bridge works the same in both directions. Many real networks are not like that. A directed graph has edges with a direction, usually drawn as an arrow from one vertex to another, used whenever a relationship runs only one way. Graphs can also be weighted, where every edge carries a number, such as a distance in kilometres, a travel time in minutes, or a transaction amount in rupees, instead of simply representing a yes/no connection. An unweighted graph, like the one built later in this chapter, treats every edge as equally costly: what matters is only how many edges you cross, not how long or expensive any single one is. Real systems frequently combine both properties at once: a road network of one-way streets with distances attached is directed and weighted simultaneously.
A graph is called connected if every vertex can reach every other vertex by following some sequence of edges; Königsberg's graph is connected, since all four landmasses can reach one another via bridges. Real networks are usually stored differently than the matrix used above, too. An adjacency matrix is simple to reason about by hand, but it wastes space: a matrix for a million-user app would need a trillion cells, even though almost all of them would be zero, since almost no pair of users is directly connected to each other. Real software almost always uses an adjacency list instead: for every vertex, just a list of the vertices it connects to directly. In Python, the natural way to write an adjacency list is a dictionary mapping each vertex to a list of its neighbours, which is exactly the representation used for the rest of this chapter.
The Graphs Hiding in Your Phone
Graphs are not confined to 18th-century bridge puzzles. Every app on your phone that shows you connections between people is secretly built on one. Take a school WhatsApp group with seven students in it: Aditi, Priya, Rohan, Meera, Kabir, Sana, and Gautam. Group membership is a relationship where direction doesn't really make sense: if Aditi shares a group with Gautam, then Gautam necessarily shares that same group with Aditi. There is no version of "being in a group together" that applies to only one side. A WhatsApp group membership is mutual by construction, which makes it a clean example of an undirected edge. If you drew an edge between every pair of students who share this one group, you would connect all seven of them to all six others, a shape called a complete graph, with every possible edge present. Seven students give 7 × 6 / 2 = 21 edges: 7 choices for one end of an edge, 6 remaining choices for the other end, divided by 2 because each edge gets counted once from each of its two ends. A complete graph is not very interesting to search, though: everyone is exactly one step from everyone else, so there is no real structure to discover.
Not every relationship on a phone is like that. Saving someone's number as a WhatsApp contact is a private action taken on your own device. It does not require the other person to do anything, and it certainly does not require them to save you back. If Meera saves Kabir's number, she can message him; whether Kabir has saved her number too is a completely separate fact that he controls on his own phone. That makes "has saved as a contact" a directed relationship: an edge from Meera to Kabir does not imply an edge back. Instagram and X (formerly Twitter) model this even more explicitly with their "follow" feature: you can follow a cricketer or a celebrity who has never heard of you and never follows back, and the app represents that perfectly well as a one-way arrow.
LinkedIn sits closer to the WhatsApp-group end of the spectrum. A LinkedIn "connection" requires both sides to accept: one person sends a request, and nothing links the two profiles until the other person clicks accept. Only after that does the edge exist, and once it does, it exists identically in both directions; nobody can be "more connected" to someone than that person is to them. That single design choice (approval required from both sides) is what turns LinkedIn's connection graph into an undirected one, the same mathematical shape as the WhatsApp group, even though the app looks nothing like a bridge map of an 18th-century Prussian city.
Measuring Distance: Breadth-First Search
Once two people are known to be connected through a chain of mutual friends, a natural next question is: how long is the shortest chain? This is exactly what LinkedIn is computing when it labels someone a "2nd-degree connection," and what any "mutual friends" feature is doing behind the scenes. In an unweighted graph, the shortest path between two vertices is simply the one crossing the fewest edges, and the standard way to find it is an algorithm called breadth-first search, or BFS.
BFS works outward in rings. Starting from one vertex, it first visits every vertex exactly one edge away, then every vertex exactly two edges away, then three, and so on, never jumping ahead to a farther vertex before every nearer one has been checked. To keep track of what to visit next, in order, BFS uses a queue: a first-in-first-out list, where whichever vertex has been waiting longest gets processed next. Because it explores strictly ring by ring, the first time BFS reaches any given vertex, it has necessarily found that vertex's shortest possible distance from the start.
The queue is doing real work here. Swap it for a stack, last-in-first-out instead of first-in-first-out, and the algorithm becomes something else entirely: depth-first search, which plunges down one path as far as it can before backtracking. Depth-first search is genuinely useful for other problems, but it does not guarantee finding the shortest path first; it might stumble onto a distant vertex through a long, winding route before ever trying the closer ones. The queue is what forces BFS to exhaust every nearer possibility before considering anything farther away.
Return to the seven classmates. Being in the same WhatsApp group connects all of them, but being actual close friends, people who talk one-on-one beyond the group chat, is a much sparser relationship. Suppose the real friendships look like this:
Aditi - Priya, Rohan
Priya - Aditi, Meera
Rohan - Aditi, Kabir
Meera - Priya, Sana
Kabir - Rohan, Sana
Sana - Meera, Kabir, Gautam
Gautam - Sana
Every name on the left lists the friends on the right, and because friendship here is undirected, each connection appears on both sides: Priya lists Aditi, and Aditi lists Priya. Aditi and Gautam, at opposite ends of this list, share no direct friends at all. How far apart are they?
Run BFS starting from Aditi. Distance 0 is Aditi herself. Her direct friends, Priya and Rohan, are distance 1, added to the queue in that order. Processing Priya first: her friends are Aditi (already visited) and Meera (new). Meera becomes distance 2. Processing Rohan next: his friends are Aditi (visited) and Kabir (new). Kabir becomes distance 2. The queue now holds Meera and Kabir, both distance 2. Processing Meera: her friends are Priya (visited) and Sana (new). Sana becomes distance 3. Processing Kabir: his friends are Rohan (visited) and Sana, but Sana was just discovered by Meera, so this is skipped, not overwritten. Processing Sana: her friends are Meera (visited), Kabir (visited), and Gautam (new). Gautam becomes distance 4. Finally, processing Gautam, whose only friend, Sana, is already visited, empties the queue and ends the search.
Aditi and Gautam are separated by four hops: Aditi → Priya → Meera → Sana → Gautam. It is worth pausing on a distinction that is easy to blur: four hops means three people stand between them (Priya, Meera, and Sana), not four. The distance counts edges crossed, and the two endpoints of the chain, Aditi and Gautam, are not "in between" anything themselves.
Turning the Trace Into Code
Hand-tracing seven names is manageable; doing the same for a social network with a billion users obviously is not. Here is the entire algorithm as working Python, using a dictionary as the adjacency list and collections.deque as the queue:
from collections import deque
def bfs_distances(graph, start):
distances = {start: 0}
queue = deque([start])
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if neighbor not in distances:
distances[neighbor] = distances[current] + 1
queue.append(neighbor)
return distances
friends = {
"Aditi": ["Priya", "Rohan"],
"Priya": ["Aditi", "Meera"],
"Rohan": ["Aditi", "Kabir"],
"Meera": ["Priya", "Sana"],
"Kabir": ["Rohan", "Sana"],
"Sana": ["Meera", "Kabir", "Gautam"],
"Gautam": ["Sana"],
}
print(bfs_distances(friends, "Aditi"))
# {'Aditi': 0, 'Priya': 1, 'Rohan': 1, 'Meera': 2, 'Kabir': 2, 'Sana': 3, 'Gautam': 4}
The distances dictionary does two jobs at once: it stores every vertex's distance from start, and its keys double as the "already visited" check, which is exactly what if neighbor not in distances is testing. Every neighbour's distance is set to one more than the vertex that discovered it, and that neighbour is added to the queue so its own neighbours get checked in their turn. Run this on the friends dictionary and the printed output matches the hand trace exactly, key by key, in the same order each name was first discovered: Aditi, then Priya and Rohan, then Meera and Kabir, then Sana, then Gautam. The whole search, visiting every vertex once and computing every distance from a single starting point, takes nine lines of code inside the function.
Try calling bfs_distances(friends, "Gautam") instead. The result gives Sana at distance 1, Meera and Kabir at distance 2, Priya and Rohan at distance 3, and Aditi at distance 4: the same four hops, just discovered in the opposite order. This isn't a fluke: it is a guaranteed property of undirected graphs. Since every edge works both ways, the shortest path from Aditi to Gautam and the shortest path from Gautam to Aditi are the same path, walked in opposite directions, so they must have the same length. Distance in an undirected graph is always symmetric, which is exactly why, if LinkedIn labels one user as another's 2nd-degree connection, the label is guaranteed to match in reverse, from a single underlying computation rather than two separate ones.
This also scales far better than it might look. Because each vertex is only ever added to the queue once (the not in distances check guarantees that), and each edge is only ever inspected from its two endpoints, the algorithm does a bounded amount of work per vertex and per edge. Computer scientists write this as O(V + E) time, meaning the running time grows in direct proportion to the number of vertices plus the number of edges, never anything larger. That is what makes it realistic for a platform like LinkedIn or Facebook to compute mutual connections between users in a network of hundreds of millions of people: the algorithm never compares every user to every other user, only to their immediate neighbours, ring by ring.
Six Degrees, Four Degrees, and the Same Idea Everywhere
The idea that distance in a human social network tends to be surprisingly small is not new. In 1967, the American social psychologist Stanley Milgram ran an experiment that has since become famous: he gave letters to volunteers scattered across the American Midwest, with instructions to get the letter to a specific stockbroker in Boston, but only by passing it, hand to hand, through people they knew personally, each one forwarding it to whichever acquaintance seemed likeliest to be closer to the target. Among the chains that made it all the way through, the typical length was around five or six links, an observation that gave rise to the popular phrase "six degrees of separation": the idea that any two people, anywhere, are connected through a surprisingly short chain of acquaintances.
Modern platforms can check this claim directly instead of relying on chains of physical letters. In 2011, researchers analysing Facebook's entire friendship graph found that the average distance between any two users was about four steps, widely reported as "four degrees of separation." By 2016, with hundreds of millions more people on the platform, researchers reran the analysis and found the average distance had actually shrunk, to roughly three and a half steps. A denser network (more edges packed among a growing number of vertices) tends to pull everyone closer together, in exactly the way adding a few more friendships to the seven-classmate graph would shorten the Aditi-to-Gautam path.
None of this machinery cares whether the vertices are river landmasses, phone contacts, or bank accounts. Indian Railways' network of stations and the direct trains linking them is a graph, and the shortest path through it is what determines the fastest route a booking service like IRCTC can offer. UPI transactions between millions of bank accounts form a graph too, and unusual patterns within it (a small cluster of accounts rapidly passing money back and forth, for instance) are precisely what fraud-detection systems are built to flag. Road networks, flight networks, the citation trail between research papers, and the "People You May Know" suggestions on a social app all start with the same two ingredients Euler used in 1736: a set of vertices, and a set of edges connecting some of them.
Which brings the chapter back to where it started. The bridges of Königsberg and a school WhatsApp group have nothing in common as objects. One is stone and water; the other is an icon on a phone screen. But as graphs, they follow identical rules. A vertex's degree, the handshaking lemma, the difference between a directed and an undirected edge, and breadth-first search for shortest paths: every one of those tools applies without modification, whether the question is whether a walk across seven real bridges is possible, or how many friends stand between you and someone you have never met. That is the entire point of Euler's original trick: throw away everything about a problem except which things are connected to which, and the resulting structure turns out to describe an astonishing range of the world, nearly three centuries later, one WhatsApp group at a time.
Key Takeaways — Summary and Recap
Let us recap what we covered: the core ideas behind graph theory and networks — from bridges to social graphs, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.