Part VII · Chance & data Chapter 46 of 60
Graphs
A walk round town: bridges, crossroads, roads and maps. Euler reduced a city to nothing but points and the lines between them, and solved the bridge problem. The same trick is used today to plan routes, draw up timetables and colour maps.
Builds on: 45 · Combinatorics
You will learn
- translate problems about bridges, roads and acquaintances into the language of graphs
- use vertex degrees to decide whether every edge of a graph can be traversed exactly once
- find a shortest path with Dijkstra’s algorithm and the cheapest road network
- use Euler’s formula to prove that a graph can’t be drawn without crossings
The last chapter ended with a walk through eighteenth-century Königsberg. The city stood on the river Pregel. In the middle of the river lay the island of Kneiphof with the cathedral (today it’s Kant Island in Kaliningrad), and a little to the east a second island, Lomse. The banks and islands were joined by seven bridges. The townspeople argued: could you walk through the city crossing each bridge exactly once? You don’t have to return to where you started, and swimming or jumping isn’t allowed.
Try it yourself before reading on. Choose where to start and tap the bridges one by one.
Seven bridges
The problem reached Leonhard Euler, then working at the St Petersburg Academy of Sciences, through Carl Ehler, the mayor of Danzig. In August 1735 Euler presented his solution to the Academy, and the paper appeared in the Academy’s Commentarii in the volume for 1736. He himself didn’t consider the problem quite mathematical. In a letter to Ehler in the spring of 1736 Euler remarked that the solution rested on reasoning alone and didn’t depend on any mathematical principle, so it wasn’t clear why it should be expected of a mathematician. This “non-mathematical” problem founded a new area of mathematics: graph theory.
Euler’s main step was to throw away everything superfluous. It doesn’t matter how wide the river is, how long the bridges are, or where the cathedral stands. All that matters is which pieces of land are joined by which bridges. Each piece of land can be shrunk to a point, each bridge to a line between two points. The result is a picture of four points and seven lines. It can be drawn as crookedly as you like: the problem won’t change. Euler himself didn’t draw pictures with points; he labelled the pieces of land with letters and the crossings of bridges with pairs of letters. But the essence is the same.
A graph is a set of points, called vertices, and lines between them, called edges. Each edge joins two vertices. All that matters is what’s joined to what; where the points stand and how the lines bend makes no difference.
Don’t confuse a graph with the graph of a function from the chapter on functions: the words are related, but the meanings differ.
In the bridge problem two vertices can be joined by several edges: the island of Kneiphof is linked to the north bank by two bridges. We allow such multiple edges. The graphs from the six guests problem, where each pair is joined by exactly one segment, are graphs too, just simple ones.
Counting ends
Euler reasoned like this. Suppose the walk exists. Look at a piece of land where it neither starts nor ends. Every time we arrive on it by a bridge, we leave it by another bridge. So the bridges of such a piece split into “in–out” pairs, and there’s an even number of them. An odd number of bridges is possible only at the start and the end of the walk.
Now count the bridges in Königsberg. Kneiphof has five, each bank has three, Lomse has three. All four numbers are odd. But there can be at most two pieces of land with an odd number of bridges: the start and the end. The walk doesn’t exist. This answer didn’t require checking a single route.
The degree of a vertex is the number of edges that leave it. Vertices are even or odd according to the parity of their degree.
Add up the degrees of all the vertices of Königsberg: $5 + 3 + 3 + 3 = 14$. There are seven bridges, and the sum is twice that. This is no coincidence.
In any graph the sum of the degrees of all the vertices equals twice the number of edges.
The idea: count the same objects in two ways. The objects are the ends of edges. Mark both ends of each edge with a dot. The picture shows the seven bridges of Königsberg, each with two dots.
The first way: go through the vertices. A vertex has as many dots as edges leaving it, that is, its degree (a loop, an edge from a vertex to itself, has its two ends counted twice; that’s how the definition of degree works). The total number of dots is the sum of the degrees: $5 + 3 + 3 + 3 = 14$.
The second way: go through the edges. Each edge has exactly two dots, so there are $2E$ of them in all. Here $7 \cdot 2 = 14$.
We’ve counted the same dots in two ways, so the results are equal: $\sum_v \deg v = 2E$. The same argument counted handshakes in the chapter on combinatorics: each handshake is an edge, and its “ends” are two hands.
In any graph the number of vertices of odd degree is even.
Split the sum of the degrees into two parts: over the even vertices and over the odd ones. The first part is even, as a sum of even numbers. The whole sum is even by the handshake lemma. So the second part, the difference of two even numbers, is even too. But it’s a sum of odd numbers, and a sum of odd numbers is even only when there’s an even number of them.
There are seven people in a group. Can each of them know exactly three of the others?
People are vertices, acquaintances are edges. The sum of the degrees would be $7 \cdot 3 = 21$, but it has to be even: it’s twice the number of edges. In a group of eight, though, each person can know exactly three others.
A graph has nine vertices: four of degree $3$, three of degree $4$ and two of degree $5$. How many edges does it have?
The sum of the degrees: $4 \cdot 3 + 3 \cdot 4 + 2 \cdot 5 = 12 + 12 + 10 = 34$. There are half as many edges: $34 / 2 = 17$.
Euler’s rule
Euler proved that the walk is impossible in Königsberg, and noted that the same count works for any city. Let’s state his result in the language of graphs. We need two more words.
A connected graph is a graph in which you can get from any vertex to any other along edges. An Eulerian path is a route that traverses each edge exactly once. If it ends where it began, it’s called an Eulerian circuit.
A connected graph has an Eulerian circuit if and only if all its vertices have even degree. It has an Eulerian path that doesn’t close up if and only if it has exactly two odd vertices; the path starts at one of them and ends at the other.
The necessity of the condition is exactly Euler’s argument about ins and outs. He considered sufficiency obvious, and a careful proof was published only in 1873, from the notes of the German mathematician Carl Hierholzer, who died young. Here’s the full proof, in both directions.
Necessity. Suppose a route exists. Take a vertex where it neither starts nor ends. Each time the route arrives there along an edge, it leaves along another, and each edge is used once. The edges of this vertex split into “in–out” pairs, so its degree is even. If the route is closed, the same holds for the starting vertex: the first exit pairs with the last entry. So a closed route has all degrees even, and for an open one only the start and end can be odd.
Sufficiency. Let the graph be connected with all degrees even. Leave any vertex $A$ and walk along unused edges wherever you like, for as long as you can. You can get stuck only at $A$: entering any other vertex, you’ve used one more of its edges than you have leaving it, and it has an even number of edges, so a free edge remains to leave by. The result is a closed route (in the picture, $A B C D A$).
If the route hasn’t covered all the edges, then some vertex on it has unused edges: otherwise the route’s edges wouldn’t be connected to the rest, yet the graph is connected. Here it’s $B$. At each vertex the route has used an even number of edges, so the number of unused ones is even too, and from $B$ one can walk another closed route along unused edges in the same way: $B E F B$.
Splice the second route into the first: on reaching $B$, first walk the second route and then continue the first. The result is a single closed route $A B E F B C D A$. Repeat until the edges run out; there are finitely many, so this will happen.
If there are exactly two odd vertices, join them by a temporary edge. Now all degrees are even, and by what we’ve proved there’s a closed route. Remove the temporary edge from it: the circuit is cut into a path that starts at one odd vertex and ends at the other.
Today Kaliningrad has five bridges where the seven stood: two didn’t survive the bombing of the Second World War, and two more were demolished and replaced by a wide highway. The degrees have changed: each bank now has two bridges and each island three. There are two odd vertices, and the walk is possible. You’ll have to start it on one island and finish on the other, though. Check this in the widget: choose “Kaliningrad today”.
For the same reason the famous “house”, a square with both diagonals and a roof, can be drawn without lifting the pencil, but only if you start at one of the bottom corners. They’re the vertices of degree three.
A connected graph has exactly four odd vertices. What’s the smallest number of “strokes” (routes, each traversing its own edges exactly once) needed to cover all its edges?
Each stroke “serves” at most two odd vertices: its start and its end. So at least two are needed. And two are enough: join two odd vertices by a temporary edge, get a graph with two odd vertices, cover it with one path and cut the path where the temporary edge was. Königsberg would need two walks.
Visiting every crossroads
Now let’s ask a similar-looking question about vertices rather than edges. Can you visit every crossroads in town, each exactly once, and come back home?
In the mid-1850s the Irish mathematician William Rowan Hamilton invented a puzzle, the Icosian Game. The vertices of a dodecahedron (a solid made of twelve pentagons) carried the names of twenty cities of the world, and you had to make a voyage round the world along the edges, visiting each city once. In 1859 Hamilton sold the rights to the game to a London toy firm for twenty-five pounds.
A Hamiltonian cycle is a cycle that passes through each vertex of the graph exactly once. If the route doesn’t have to return to the start, it’s called a Hamiltonian path.
For edges Euler gave a simple test: count the degrees and everything is clear. For vertices nobody knows such a test. The dodecahedron has thirty Hamiltonian cycles (not distinguishing where you start or which way you go). But the graph described in 1898 by the Danish mathematician Julius Petersen has none at all, even though all its vertices are alike, each has three neighbours, and the graph looks no worse than the dodecahedron. The easiest way to confirm this is a search: a computer does it in an instant, but for a graph with a thousand vertices such a search would drag on for centuries.
Here runs one of the deepest borders in mathematics. If someone shows you a route, checking that it’s Hamiltonian is easy: walk along it and tick off the vertices. But for finding one, nobody knows a method fundamentally better than a search: all known algorithms take, in the worst case, a time that grows exponentially with the number of vertices. In 1972 Richard Karp put the Hamiltonian cycle problem on his famous list of problems that are all equally hard: if a fast way to solve one is found, they’ll all be solved fast. Whether “easy to check” always means “easy to find” is the P versus NP question, one of the Millennium Problems. We’ll come back to it in the last chapter of the course.
Trees
Let’s look at graphs without cycles. A family tree, the folders on a computer, a river with its tributaries: in each case exactly one road leads from one vertex to another, and you can’t go round in a circle.
A tree is a connected graph without cycles. A vertex of degree one is called a leaf.
A tree with $V$ vertices has exactly $V - 1$ edges.
First let’s make sure that a tree with at least two vertices has a leaf. Walk from any vertex along edges, never going back along the edge you’ve just used. You can’t arrive at a vertex you’ve already visited: that would make a cycle, and a tree has none. There are finitely many vertices, so the walk comes to an end, at a vertex with no other edges, that is, at a leaf.
Pluck this leaf together with its only edge. What’s left is still connected (the leaf lay on no path between other vertices) and still without cycles, so it’s a tree again. It has one vertex fewer and one edge fewer, so the difference “vertices minus edges” hasn’t changed: $7 - 6 = 6 - 5$.
Keep plucking leaves until one vertex remains. At each step the difference “vertices minus edges” stays the same, and at the end it equals $1 - 0 = 1$.
So it equalled one from the very start: $V - E = 1$, that is, $E = V - 1$.
A graph without cycles consists of three separate trees and has $30$ vertices in all. How many edges does it have?
If the trees have $a$, $b$ and $c$ vertices, they have $a - 1$, $b - 1$ and $c - 1$ edges. In all, $(a + b + c) - 3 = 30 - 3 = 27$.
How many trees can be built on $n$ numbered vertices
Exactly $n^{n-2}$ different trees can be built on $n$ numbered vertices.
The answer is surprisingly simple. On three vertices there are $3^1 = 3$ trees (depending on which vertex is in the middle), on four $4^2 = 16$, on ten a hundred million. This is called Cayley’s formula: Arthur Cayley published it in 1889, although an equivalent result appears in Carl Borchardt’s work back in 1860. The idea of the most beautiful proof, proposed by Heinz Prüfer in 1918, is to encode each tree as a word of $n - 2$ vertex numbers. Pluck the leaf with the smallest number and write down the number of its neighbour, and do this $n - 2$ times. There are exactly $n^{n-2}$ words of $n - 2$ numbers, and the tree can be recovered uniquely from the word. Checking this uniqueness takes a couple of pages of careful reasoning, so we don’t give it in full here; it can be found in any graph theory textbook.
The shortest path
The satnav in your phone solves a problem about a graph: crossroads are vertices, streets are edges, and each edge has a length or a travel time.
A weighted graph is a graph each of whose edges carries a number, its weight: the length of a road, a travel time, the cost of laying a cable. The length of a route is the sum of the weights of its edges.
How do you find the shortest route without trying them all? In 1956 the Dutch programmer Edsger Dijkstra wanted to show the public what the new ARMAC computer could do, and chose a problem that needed no explanation: the shortest path between towns in the Netherlands. By his own account, he came up with the algorithm in about twenty minutes, without pencil or paper, while sitting with his fiancée on a café terrace in Amsterdam. For the demonstration he used a simplified map of $64$ towns, so that a town’s number fitted into six binary digits. The paper came out in 1959.
The idea of the algorithm is this. Spread out from the starting vertex like a wave. Each vertex carries a label, the best known time to reach it: zero at the start, infinity everywhere else. At each step take the unvisited vertex with the smallest label and declare its label final. Then check its neighbours: if going through it reaches a neighbour faster than what’s recorded, correct the neighbour’s label.
If all edge weights are non-negative, the label of the vertex the algorithm has just chosen equals the length of the shortest path to it.
Labels are never smaller than the true distances: each label is the length of some real path the algorithm has found. Suppose the algorithm has chosen the vertex $v$ with label $d$, and all the vertices chosen earlier already have correct labels. Take any path $P$ from the start to $v$. It begins at a visited vertex and ends at $v$, which isn’t yet visited; let $u$ be the first unvisited vertex on $P$, and $w$ the visited vertex just before it. When the algorithm visited $w$, its label was already correct, that is, at most the length of the part of $P$ from the start to $w$; at that moment the algorithm also checked the edge $w$–$u$ and made the label of $u$ at most the length of the part of $P$ from the start to $u$. The weights are non-negative, so this part is no longer than the whole of $P$. And $v$ was chosen as the unvisited vertex with the smallest label, so $d$ is at most the label of $u$. Altogether $d \le$ the length of $P$ for every path $P$, that is, $d$ is the length of the shortest path.
Another question about the same map: how do you join all the crossroads with a network of roads (or cables, or pipes) so that you can get from anywhere to anywhere and the network costs as little as possible? Such a network needs no superfluous roads: if it contains a cycle, one edge of the cycle can be removed and it stays connected. So the cheapest network is a tree.
A spanning tree of a graph is a tree made of its edges and passing through all its vertices. A spanning tree of the smallest total weight is called minimal.
The first to solve this problem was the Czech mathematician Otakar Borůvka in 1926: he was helping to design an electricity network for Moravia. The simplest method was described in 1956 by the American Joseph Kruskal: take the edges in order of increasing weight and skip those that would close a cycle. Greed, which usually lets you down, doesn’t let you down here, and here’s why.
Split the vertices of a connected weighted graph into two groups. The cheapest edge between the groups belongs to some minimal spanning tree.
The dashed line splits the vertices into two groups. Three edges run between the groups; the cheapest of them, $e$, costs $2$.
Take a spanning tree $T$ that doesn’t contain $e$ (in the picture, a tree costing $13$). Let’s show that it can be replaced by a tree containing $e$ that costs no more.
Add $e$ to the tree. Its ends were already joined by a path in $T$, so exactly one cycle has appeared. The cycle crosses the dashed line along $e$ and must get back to its own side, so it crosses it once more, along some edge $f$ of the tree $T$. Since $e$ is the cheapest edge across the dashed line, $f$ is no cheaper: here $4 \ge 2$.
Remove $f$. The cycle is broken, the graph stays connected (the rest of the cycle now does the job of $f$), and there are again $V - 1$ edges: we have a spanning tree. Its cost, $13 - 4 + 2 = 11$, is no greater than before.
Now let $T$ be a minimal tree. If $e$ isn’t in it, the swap gives a tree that costs no more, so it’s minimal too, and it contains $e$. This proves Kruskal’s method correct: each edge it takes joins some already built piece of the network to the other vertices and is cheaper than all the edges across that border, since all the cheaper ones have already been considered. By the lemma such an edge can be taken without losing out on cost.
Practise: here are problems on degrees, routes and shortest paths. The maps are small, so you can run Dijkstra in your head.
Three houses, three wells
An old puzzle: a village has three houses and three wells. Each owner wants to tread a path to each well, but the neighbours have fallen out and don’t want their paths to cross. Can all nine paths be laid out like that? Another version: five towns, and every two must be joined by a road without crossroads or bridges.
A planar graph is a graph that can be drawn in the plane so that edges meet only at vertices. A graph with $n$ vertices where every two are joined by an edge is called complete and written $K_n$. A graph with two groups of vertices whose edges run only between the groups is called bipartite; three houses and three wells with all the paths make $K_{3,3}$.
However you drag, $K_{3,3}$ and $K_5$ keep at least one crossing. To prove it’s not just clumsiness on our part, we need a formula Euler discovered in 1750 while studying polyhedra. Draw a connected graph in the plane without crossings. The edges cut the plane into pieces.
A face of a plane drawing of a graph is each of the pieces into which the edges cut the plane. The outer, infinite piece counts as a face too.
If a connected graph is drawn in the plane without edges crossing, then $V - E + F = 2$, where $V$ is the number of vertices, $E$ the number of edges and $F$ the number of faces.
Choose a spanning tree in the graph. It has $V$ vertices and $V - 1$ edges, and one face, the whole plane: without cycles nothing can be cut off from it. That gives $V - (V - 1) + 1 = 2$. In the picture it’s the graph of a cube, flattened onto the plane: $8 - 7 + 1 = 2$.
Add one of the remaining edges. Its ends are already joined by a path in the tree, so the new edge together with that path closes a cycle. A cycle is a closed line without self-intersections, and it divides the plane into an inside and an outside (this seems obvious, but a rigorous proof isn’t easy: it’s the Jordan curve theorem; for polygonal lines the proof is short). The face the edge ran through has split in two: there’s one more face. There’s also one more edge, and $V - E + F$ hasn’t changed: $8 - 8 + 2 = 2$.
The same with each further edge: it runs inside one face and joins two points of its boundary, so it cuts that face in two. $E$ and $F$ grow together, and the sum doesn’t change. When all the edges have been added, the cube has $8 - 12 + 6 = 2$.
We started with the sum $2$ and never changed it. So for any connected graph drawn in the plane without crossings, $V - E + F = 2$.
Euler’s formula implies that a plane graph can’t have too many edges.
A simple planar graph (without multiple edges or loops) with $V \ge 3$ vertices has at most $3V - 6$ edges. If moreover it has no triangles, it has at most $2V - 4$ edges.
It’s enough to prove this for a connected graph: a disconnected one can be made connected by adding edges, and that only increases the number of edges. If there are fewer than three edges, the inequalities hold automatically ($E \le 2 \le 3V - 6$ and $2 \le 2V - 4$ for $V \ge 3$). Suppose there are at least three edges, and draw the graph without crossings.
Go round each face along its boundary and write down how many edges you meet; add these numbers over all the faces. Each edge is counted in the sum exactly twice, once from each of its sides (if the same face lies on both sides, twice in going round that face). So the sum equals $2E$. On the other hand, the boundary of each face contains at least three edges: a face with one edge is a loop, one with two edges means two edges between the same vertices, and a simple graph has neither. So the sum is at least $3F$, and $3F \le 2E$.
By Euler’s formula $F = 2 - V + E$. Substituting: $3(2 - V + E) \le 2E$, that is, $6 - 3V + 3E \le 2E$, so $E \le 3V - 6$. If there are no triangles, the boundary of each face contains at least four edges, and the same argument gives $4F \le 2E$, $4(2 - V + E) \le 2E$, so $E \le 2V - 4$.
Neither five points joined each to each nor three houses with three wells can be drawn in the plane without crossings.
$K_5$ has $5$ vertices and $\binom{5}{2} = 10$ edges. If it were planar, by the previous corollary it would have at most $3 \cdot 5 - 6 = 9$ edges. A contradiction.
$K_{3,3}$ has $6$ vertices and $3 \cdot 3 = 9$ edges. It has no triangles: of the three vertices of a triangle, two would be in the same group (houses or wells), and there are no edges within a group. So a planar $K_{3,3}$ would have $E \le 2 \cdot 6 - 4 = 8$. But there are nine edges: a contradiction. No amount of dexterity in the widget will help: at least one crossing always remains.
A convex polyhedron has $12$ vertices and $30$ edges. How many faces does it have?
By Euler’s formula $F = 2 - V + E = 2 - 12 + 30 = 20$. It’s the icosahedron: twenty triangular faces. A check by counting edges: twenty triangles have $60$ sides, and each edge is a side of two faces, so there are $60 / 2 = 30$ edges.
It turns out that $K_5$ and $K_{3,3}$ are the only real obstacles.
A graph is planar if and only if it contains no $K_5$ or $K_{3,3}$, where some edges may be subdivided into chains by intermediate vertices.
We’ve already proved half of the theorem: if a graph contains $K_5$ or $K_{3,3}$ (even with edges subdivided into chains), it isn’t planar, since a drawing of the graph without crossings would give such a drawing for them too. The converse, proved by the Polish mathematician Kazimierz Kuratowski, is much more delicate: from a graph without such “forbidden pieces” one has to build a drawing without crossings. The proof takes several pages of case analysis and is beyond the scope of this chapter; it can be found in graph theory textbooks, for example R. Diestel’s.
And what if the village isn’t on a plane? On the surface of a doughnut, a torus, three houses can be joined to three wells without a single crossing: some paths go “round the hole”. Switch on the drawing on a torus in the widget. Euler’s formula changes on the torus too: there $V - E + F = 0$. The number on the right depends only on the surface, and the chapter on topology will tell you all about it.
Four colours
In 1852 Francis Guthrie was colouring a map of the counties of England and noticed that four colours were enough to keep neighbouring counties always different colours. He asked his brother Frederick, a student of Augustus De Morgan, whether this was true for every map. On 23 October 1852 De Morgan wrote to Hamilton about the question. So began a problem that took more than a hundred and twenty years to solve.
A map is easily turned into a graph: put a capital dot in each country and join the capitals of neighbouring countries. Neighbours are countries sharing a stretch of border. Touching at a single point doesn’t count: in the USA four states, Utah, Colorado, Arizona and New Mexico, meet at their corners at one point, but Utah and New Mexico aren’t neighbours. If points counted too, a cake cut from the centre into forty slices would need forty colours. The graph of a map is always planar: the edges can be drawn from capital to capital through the shared borders so that they don’t cross.
The chromatic number of a graph is the smallest number of colours with which its vertices can be coloured so that the ends of each edge have different colours.
Three colours aren’t always enough. If a country is surrounded by a ring of five neighbours, the ring itself needs three colours (with two they’d alternate, and five is odd), and the central country needs a fourth. But a fifth, as it turned out, is never needed.
The vertices of any planar graph can be coloured with four colours so that the ends of each edge have different colours. In other words, any map in the plane can be coloured with four colours.
We won’t prove this theorem here: its proof runs to hundreds of pages plus a computer search. The idea is this: find a finite list of special pieces of a map, at least one of which is bound to occur in any map, and for each piece show that it can be “shrunk”, the smaller map coloured, and the piece put back without spoiling the colouring. Then by induction the colours suffice for all maps. The whole difficulty is finding the list and checking each piece.
The story of the proof reads like a detective novel. In 1879 the English lawyer and mathematician Alfred Kempe published a proof, and for eleven years it was considered correct. In 1890 Percy Heawood found an error in it, but rescued what could be rescued from Kempe’s argument: five colours are always enough. Four colours were proved only in 1976, by Kenneth Appel and Wolfgang Haken. They reduced the problem to checking almost two thousand special pieces of maps, and a computer checked them for over a thousand hours. Many mathematicians were unhappy: a proof no human could read in full didn’t seem quite a proof. In 1996 Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas found a simpler route with 633 cases, but also with a computer. And in 2005 Georges Gonthier checked the entire proof in the Coq system, which verifies every logical step formally. There’s no doubt left.
Colouring isn’t only for mapmakers. Make a graph of exams: the vertices are exams, with an edge if some student sits both. The colours are the days of the exam period. A colouring without conflicts is a timetable in which nobody has two exams on the same day, and the chromatic number is the smallest number of days. Sudoku is a colouring too: $81$ cells, nine colours, and cells in the same row, column or box are joined by edges. Only timetable graphs usually aren’t planar, and four colours may not be enough for them.
It’s a small world
The last stop is the biggest graph we’ve seen: the graph of acquaintances of all the people on Earth. In 1967 the American psychologist Stanley Milgram asked residents of Nebraska and Kansas to forward a letter to a stranger in Massachusetts, but only through acquaintances they knew by first name. Only some of the letters arrived, but those that did had passed through just five or six hands on average. That’s where the phrase “six degrees of separation” comes from.
In 2011 researchers from Facebook and the University of Milan computed the distances in the friendship graph of all the network’s active users: about $721$ million vertices and tens of billions of edges. The average distance between two people turned out to be $4.74$ edges. Mathematicians have long used their own scale of this kind: the Erdős number, the distance to Paul Erdős in the co-authorship graph. For Erdős himself, who wrote about fifteen hundred papers with hundreds of co-authors, it’s zero; for his co-authors it’s one, for their co-authors two, and so on. Most mathematicians who have such a number at all have one no greater than five.
A graph forgets everything except connections: distance, shape, colour. That’s why the same theorems work for bridges, roads, maps, acquaintances and timetables. To solve a problem it’s often enough to spot the graph in it.
Where next
Picture a town whose streets form an infinite square grid. A walker leaves home and at every crossroads picks one of the four directions at random by tossing a coin twice. Will they ever get back home? And if the town is three-dimensional, built of identical cubes, with six directions at every crossroads?
The graph here is as simple as can be, and the question is about chance: which routes are more likely, and what will happen “almost surely”. The answer, found by George Pólya in 1921, is surprising: on a line and in the plane the walker returns with probability one, but in space there’s a considerable chance they never come back. What probability is, how to compute it and where intuition about chances lets you down is the subject of the next chapter.