Ramsey theory: the party problem
At any party of six people, there are always three who all know each other, or three who are all strangers to each other. Always, however the friendships fall. With five people, that's no longer guaranteed.
Make each guest a vertex and join every pair with an edge: teal if they're friends, pink if they're strangers. That's the complete graph K6 with every edge coloured one of two colours. The claim is that there's always a monochromatic triangle: three vertices whose three edges all have the same colour.
Five people: no single-colour triangle
Six people: the proof
Why six always works. Pick any person v. They have 5 edges to the others, each teal or pink, so at least 3 must share a colour. Say v is friends with a, b and c (if it's strangers instead, swap the colours in what follows). Now look at the three edges among a, b and c:
- If any of them is teal, say a–b, then v, a and b are three mutual friends.
- If none of them is teal, then a, b and c are three mutual strangers.
Either way there's a single-colour triangle. Combined with the five-person example, this shows that 6 is the exact threshold. We write R(3, 3) = 6.
Ramsey numbers
R(s, t) is the smallest number of people that guarantees either s mutual friends or t mutual strangers. Frank Ramsey proved in 1930 that these numbers always exist.
The big idea of Ramsey theory is that complete disorder is impossible: any large enough structure contains a perfectly organised piece. But the exact numbers are fiendishly hard to find. R(4, 4) = 18 has been known since 1955. For R(5, 5), all anyone knows is that it's somewhere from 43 to 46, and checking every possible colouring is far beyond any computer. The mathematician Paul Erdős liked to joke that if aliens threatened to destroy Earth unless we told them R(5, 5), we should put all our computers and mathematicians to work on it; but if they asked for R(6, 6), we should try to destroy the aliens instead.
Try it. Using the handshake idea, explain why in any group of 6 people, if each person shakes hands with exactly 3 others, there's either a trio who all shook hands or a trio where nobody shook hands with each other.
Show answer
This is just a special case of R(3, 3) = 6: colour each pair teal if they shook hands and pink if not. Any 2-colouring of K6 has a single-colour triangle, so one of the two kinds of trio must exist, whatever the handshakes were.
Random graphs
What does a "typical" graph look like? In 1959 and 1960, Paul Erdős and Alfréd Rényi studied graphs built by chance: take n vertices and, for each pair, flip a biased coin to decide whether to add an edge. The key number is the average degree, the average number of edges per vertex.
Average degree 0.5small scattered pieces; largest has 5
Average degree 1.5a giant piece appears: 29 of 40
Average degree 4almost everything is joined: 39 of 40
Erdős and Rényi discovered that random graphs change suddenly, like water freezing into ice:
- With average degree below 1, the graph is a dust of small pieces, mostly little trees.
- Just past average degree 1, a giant component appears, containing a sizeable fraction of all vertices. On large graphs this switch is remarkably sharp.
- Around average degree ln n (the natural logarithm of the number of vertices), the last isolated vertices join and the graph becomes connected.
These "phase transitions" explain things like epidemics. If each infected person passes a disease on to fewer than one other person on average, outbreaks fizzle out in small clusters. Above one, a giant outbreak becomes possible. That's why the reproduction number "R" above or below 1 matters so much.
Small worlds
In Unit 2 we met the "six degrees of separation" idea. How can billions of people be so close together when most of our friends live near us and know each other? In 1998 Duncan Watts and Steven Strogatz gave a beautifully simple explanation.
Only local friends
Three long-range shortcuts
Real social networks combine two features that seem to pull in opposite directions:
- High clustering: your friends tend to be friends with each other, like the neighbourhoods on the circle.
- Short distances: any two people are linked by a short chain.
Watts and Strogatz showed that a tiny number of random long-range links (a friend who moved abroad, a colleague from another city) is enough to make distances short, while barely affecting clustering. In a network of millions, a small fraction of shortcuts brings typical distances down from thousands of steps to a handful. Graphs with both properties are called small-world networks. They describe social networks, the nerve connections of a worm, power grids and more.
Hubs and scale-free networks
Random graphs have a democratic feel: most vertices have roughly the average degree. Real networks often don't. On the web, in airline routes and in social media, a few hubs have enormous numbers of connections while most vertices have only a few.
In 1999 Albert-László Barabási and Réka Albert suggested a simple mechanism: preferential attachment. Networks grow over time, and newcomers prefer to link to vertices that are already popular. New websites link to famous websites; new airports add flights to big hubs. The result is a heavily unequal degree distribution, sometimes called scale-free, in which hubs are far more common than in a random graph.
Hubs have a double-edged effect. Networks with hubs are robust against random failures (most vertices are unimportant, so losing a random one rarely matters) but fragile against targeted attacks (remove the few hubs and the network shatters). That's why airline disruptions at one hub airport ripple across a whole continent, and why vaccinating highly connected people can slow an epidemic far more than vaccinating people at random.
Who matters most? Centrality
"Important" can mean different things in a network, and each meaning gives a different measure, called a centrality:
| Centrality | Idea | Top in the picture |
|---|---|---|
| Degree | How many direct connections? (Unit 1) | c and d (3 each) |
| Closeness | How short are your distances to everyone else? Related to eccentricity in Unit 2. | Sam |
| Betweenness | How many shortest paths between other people pass through you? | Sam (all 9 paths between the two groups) |
| Eigenvector / PageRank | Are you connected to people who are themselves important? | see the next section |
Betweenness picks out brokers and bottlenecks: the person whose departure would split a team, or the road junction where traffic jams form. Notice that Sam is a cut vertex (Unit 2), exactly the kind of weak spot betweenness tends to find.
PageRank
In the late 1990s, web search engines struggled to tell important pages from unimportant ones. Larry Page and Sergey Brin, then students at Stanford, had a graph-theoretic idea that became the foundation of Google: a page is important if important pages link to it.
That sounds circular, and it is, but in a useful way. Imagine a "random surfer" who starts on any page and keeps clicking a random link. Occasionally (15% of the time, in the original paper) they get bored and jump to a completely random page instead. Over a long time, the fraction of time the surfer spends on each page is its PageRank.
Two lessons hide in this small example:
- Quality beats quantity. A, with one link from the best page, outranks D, with links from two modest pages.
- Links are votes, shared out. A page divides its importance among all the pages it links to. C passes everything to A; B splits its share between C and D.
Mathematically, the PageRank scores are the solution of a large system of equations, which can be written as a special vector of the graph's adjacency matrix (Unit 1), called an eigenvector. Studying graphs through their matrices is a whole field, spectral graph theory, which also helps split networks into communities and measure how quickly a random walk mixes. Search engines today use many more signals, but the random-surfer idea remains one of the most famous applications of graph theory.
Try it. Suppose page E above adds a link to itself from a new page F, and nothing links to F. Would E's PageRank go up much? What does this say about spam pages that link to each other?
Show answer
Only a little. F receives only random jumps, so it has very little importance to pass on. Links from unimportant pages are worth little, which is exactly why PageRank resisted simple tricks like creating many junk pages that all link to one target, at least much better than counting links did.
Where to go next
You now know the core of a first university course in graph theory. Here are some directions to explore:
- Algorithms in depth: how fast each method runs, data structures like heaps that make Dijkstra fast, and what "NP-complete" really means.
- Extremal graph theory: how many edges can a graph have before a triangle (or any pattern) is forced? Turán's theorem is a beautiful starting point.
- Graph minors and structure: the deep theory, developed by Neil Robertson and Paul Seymour, that grew from Kuratowski's theorem.
- Network science: communities, epidemics on networks and the analysis of real data.
- Graphs in machine learning: graph neural networks learn from molecules, road maps and social networks directly.
Books
- Richard J. Trudeau, Introduction to Graph Theory (Dover). Short, friendly and written for people with no background. A natural next step.
- Robin J. Wilson, Introduction to Graph Theory. A classic, clear undergraduate text.
- Douglas B. West, Introduction to Graph Theory. Thorough and rigorous, with many exercises.
- Reinhard Diestel, Graph Theory. Advanced and elegant; the author makes an electronic edition freely available.
- Albert-László Barabási, Network Science. The science of real-world networks, free to read online.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. Show that in any group of 6 people, there are actually at least two single-colour triangles. (Hard; just try to see why one isn't the end of the story.)
Show answer
A known result (Goodman's formula) says every 2-colouring of K6 contains at least two single-colour triangles. One way in: count "two-coloured corners", places where a vertex has one teal and one pink edge. Each vertex has 5 edges, so at most 3 × 2 = 6 such corners. That's at most 36 in total. Every non-single-colour triangle has exactly 2 such corners, so there are at most 18 of them. Of the 20 triangles in K6, at least 20 − 18 = 2 are single-coloured.
2. A random graph has 1,000 vertices and 400 edges. Do you expect a giant component?
Show answer
The average degree is 2 × 400 ÷ 1000 = 0.8, below 1. No: expect many small pieces, mostly trees.
3. In the broker picture, what happens to the network if Sam leaves? Which unit's idea is this?
Show answer
The network splits into two components, {a, b, c} and {d, e, f}. Sam is a cut vertex, and the edges c–Sam and Sam–d are bridges (Unit 2).
4. Why might a network with hubs survive 50% of its vertices failing at random but collapse if 5% are deliberately attacked?
Show answer
Random failures mostly hit the many low-degree vertices, which hold little together. A deliberate attack targets the few hubs, which carry most of the connections, so removing them breaks the network into fragments.
5. In the PageRank example, which page would gain the most if B added a link to E?
Show answer
E, which currently has no incoming links: its score rises from about 3% to about 8%. B now splits its importance three ways (C, D, E) instead of two, so everyone else drops slightly. For example, C falls from about 35% to 34%.
Course summary
Congratulations on reaching the end of the course. Here is the whole journey on one line each:
- Foundations: vertices, edges, degree and the handshake lemma.
- Walks and connectivity: paths, components, distance, bridges and cut vertices.
- Trees: n − 1 edges, spanning trees, Kruskal and Prim.
- Exploring a graph: BFS, DFS and topological sorting.
- Shortest paths: Dijkstra, Bellman–Ford and Floyd–Warshall.
- Euler and Hamilton: every edge once is easy; every vertex once is hard.
- Matching: augmenting paths, Hall's theorem and stable matchings.
- Network flow: maximum flow equals minimum cut.
- Colouring: chromatic number, greedy colouring and four colours for maps.
- Planar graphs: V − E + F = 2, K5, K3,3 and the Platonic solids.
- Beyond: Ramsey theory, random graphs, small worlds, hubs and PageRank.
The same simple picture, dots and lines, turned out to describe friendships, roads, mazes, schedules, pipes, maps, molecules and the web. Next time you look at a metro map, a family tree or a list of who follows whom, you'll see the graph underneath.