Graph Theory: Networks, scheduling, map coloring, and Ramsey numbers

When you ask your phone for directions across town, an answer comes back almost at once. Think about what that answer claims. Out of all the ways to get from where you are to where you're going, this one is the fastest, or close to it. How could software know that without checking every possible route?

Checking every route isn't an option. Even a small town has thousands of intersections, and the number of possible routes between two of them grows explosively with the size of the network. A route can turn left or right at each intersection, and the choices multiply. For a whole region, listing every route would take longer than anyone would wait.

The first step is to see the road network as a graph: a collection of points, called vertices, joined by lines, called edges. Each intersection is a vertex, and each stretch of road between two intersections is an edge. Then each edge gets a number: the time it takes to drive, given its length and speed limit. Finding the fastest route becomes finding the path between two vertices whose numbers add up to the smallest total.

In 1959 the Dutch computer scientist Edsger Dijkstra published a short method for exactly this problem: finding the path of minimum total length between two given points in a network (Dijkstra 1959). His method doesn't check every path. It works outward from the starting point:

• Settle the closest point whose shortest distance from the start isn't yet known.
• Use that point to update the best-known distances to its neighbors.
• Repeat until the destination is settled.

Each point is settled once, in order of its distance from the start. When the destination is settled, its shortest route is known, and most of the network's possible routes were never examined one by one.

Dijkstra's method is still the standard starting point for this problem. On a road network as large as Western Europe's, with about 18 million vertices, the basic method takes around two seconds per query on researchers' test machines, too slow for a service answering many requests at once. Researchers have built faster techniques on top of it that do some work in advance and can then answer driving queries at continental scale in milliseconds or less. Several of these techniques have found their way into production systems (Bast et al. 2015).

That is what graph theory offers here: a way to answer questions about huge networks without examining every possibility. The same structure, points joined by weighted connections, describes internet traffic, delivery networks, and supply chains, and the same kind of reasoning applies to each.

This content reflects the field as of October 2026.

References

• Bast, Hannah, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2015. "Route Planning in Transportation Networks." arXiv:1504.05140. Updated version of Microsoft Research Technical Report MSR-TR-2014-4.
  • Free: arXiv 1504.05140
• Dijkstra, E. W. 1959. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390.
  • Free: CWI Repository (PDF)
  • Publisher: Springer

Introduction

A delivery company wants the cheapest way to move goods from a warehouse to a store. An internet router needs to send data toward its destination. A driver wants the fastest way home. These are the same mathematical problem in different clothes.

This reading covers weighted graphs, shortest paths, how Dijkstra's method finds them, and where shortest-path reasoning is used.

Networks with Numbers on Their Edges

A graph is a collection of points, called vertices, joined by lines, called edges, in which only which points are joined matters. A network is any system of connected things, such as roads, computers, or people, described as a graph. Many network questions need more than connections, though. They need costs.

A weighted graph is a graph whose edges carry numbers, called weights, such as distance, travel time, or cost. In a road network the weight might be minutes of driving. In a shipping network it might be dollars per container.

A shortest path is a route between two vertices whose edge weights add up to the smallest possible total. "Shortest" here means smallest total weight, so it can mean fastest or cheapest as well as shortest in distance.

Dijkstra's Idea in Words

In 1959 Edsger Dijkstra published a method for finding the path of minimum total length between two given points (Dijkstra 1959). It's an algorithm: a finite list of exact instructions that turns any valid input into an output in a finite number of steps. Here are its steps in words.

1. Start with the starting point settled at distance 0. Every other point has no known distance yet.
2. Look at the edges from the point you just settled. For each neighbor, add the edge's weight to the settled point's distance. If that total beats the neighbor's best-known distance, record it.
3. Among all unsettled points with a known distance, settle the one with the smallest distance.
4. Repeat steps 2 and 3 until the destination is settled.

Here is a small example. Four places are joined by roads with these travel times in minutes: Home to A, 4; Home to B, 1; A to B, 2; A to Work, 1; B to Work, 6.

The fastest route is Home to B to A to Work, 4 minutes. The direct-looking route through B alone takes 7. The method never needed to list the routes; it settled each place once, in order of distance.

The method relies on weights never being negative. Once the closest unsettled point is chosen, no detour through farther points can reach it more cheaply. Dijkstra also noted that his method needs to keep track of only some of the edges at a time, and that it seemed to need considerably less work than a method then in use (Dijkstra 1959).

Where Shortest Paths Are Used

Shortest-path reasoning turns up wherever a network has costs:

Navigation services rely heavily on Dijkstra's method and on faster techniques built on it. On a road network of Western Europe with about 18 million vertices, the basic method takes around two seconds per query on researchers' test machines. Techniques that do some work in advance can answer such queries in milliseconds or less, and several have found their way into production systems (Bast et al. 2015).

The internet relies on the same idea. In OSPF, a widely used standard for routing inside large networks, each router builds a map of the network and "constructs a tree of shortest paths with itself as root," which it uses to decide where to send data (Moy 1998, sec. 1.1).

Social and Supply Networks

Not every network question is about the cheapest route. Social networks are graphs in which people are vertices and relationships are edges. Supply networks are graphs in which firms are vertices and supplier relationships are edges. Questions about them include how many steps separate two people, which vertices sit on many shortest paths and so act as bridges, and which single failure would cut a network into pieces. Each is a question about the graph's structure, and each draws on the same vocabulary of vertices, edges, and paths.

Conclusion

Many network problems reduce to finding a shortest path in a weighted graph. Dijkstra's 1959 method solves that problem without listing routes, and faster techniques built on it now handle networks with millions of points. Questions about who connects to whom in social and supply networks use the same graph-theoretic framework.

This content reflects the field as of October 2026.

Key Terms

• Network: Any system of connected things, such as roads, computers, or people, described as a graph.
• Weighted graph: A graph whose edges carry numbers, called weights, such as distance, travel time, or cost.
• Shortest path: A route between two vertices whose edge weights add up to the smallest possible total.
• Algorithm: A finite list of exact instructions that turns any valid input into an output in a finite number of steps.

References

• Bast, Hannah, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2015. "Route Planning in Transportation Networks." arXiv:1504.05140. Updated version of Microsoft Research Technical Report MSR-TR-2014-4.
  • Free: arXiv 1504.05140
• Dijkstra, E. W. 1959. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390.
  • Free: CWI Repository (PDF)
  • Publisher: Springer
• Moy, J. 1998. "OSPF Version 2." RFC 2328. Internet Engineering Task Force.
  • Free: RFC Editor

Introduction

Every exam season, a school has to fit its exams into as few time slots as possible without making any student sit two exams at once. The problem looks like a puzzle about calendars. It's really a problem about coloring the points of a graph.

This reading covers how scheduling turns into graph coloring, what the fewest colors means, other places the same idea is used, and why the best schedule is hard to find.

From Exams to Colors

Start with the exams. Make each exam a vertex, a point in a graph. Join two exams with an edge, a line, whenever at least one student is taking both. The edge means the two exams can't be held at the same time.

A graph built this way is a conflict graph: a graph whose vertices are tasks or events and whose edges join pairs that can't happen at the same time. In general terms, two jobs are joined by an edge if they "cannot be executed at the same time" (Marx 2004).

Now give each time slot a color. A schedule assigns a color to each exam, and it works only if no edge joins two exams of the same color. That's graph coloring: assigning colors to the vertices of a graph so that any two vertices joined by an edge get different colors. The colors stand for the available time slots (Marx 2004).

Here's an example with five exams:

Art, Biology, and Chemistry all conflict with one another, so they need three different slots. Three slots are enough for everything: Art and Drama in slot 1, Biology and Economics in slot 2, Chemistry in slot 3.

The Fewest Colors Is the Fewest Slots

The chromatic number of a graph is the fewest colors needed to color it so that every edge joins two different colors (Marx 2004). In the exam example it's 3. Two colors can't work, because Art, Biology, and Chemistry are all joined to one another, and three mutually joined vertices need three colors.

In scheduling terms, the chromatic number of the conflict graph is the fewest time slots that let every exam run without a clash. Finding it answers the school's question exactly.

Maps give another view of the same idea. Make each region of a map a vertex, and join two regions that share a border. Coloring the map so neighbors differ is coloring this graph. The four color theorem says that the regions of any flat map can be colored with only four colors, so this kind of graph never needs more than four (Gonthier 2008).

The Same Idea Elsewhere

Many problems share this structure:

Frequency assignment for base stations is one of the scheduling-type problems that coloring models (Marx 2004). In register allocation, a compiler, the program that translates code into machine instructions, must keep working values in a processor's small set of fast storage slots, called registers. Two values conflict if they're needed at the same time. In a 1982 paper, G. J. Chaitin of IBM Research described a compiler that builds this conflict graph and tries to color it with as many colors as the processor has registers. When that fails, some values are moved out to slower memory (Chaitin 1982).

Why the Best Schedule Is Hard to Find

For a small graph, you can find the chromatic number by trying colorings. For large graphs, that approach breaks down. Determining the chromatic number of a graph is NP-hard (Marx 2004). Roughly, that means no known method finds it quickly for every large graph, and finding one would settle a famous open question in computer science.

In practice, schedulers settle for good-enough methods: procedures that quickly find a coloring that works, though not always one with the fewest colors. Researchers also study approximation algorithms. An approximation algorithm is a method that finds a solution with a guarantee of how far it can be from the best one (Marx 2004).

Conclusion

Scheduling conflicts turn into a coloring problem: conflicts become edges, time slots become colors, and the fewest slots becomes the chromatic number. The same model assigns radio frequencies and processor registers. Finding the exact chromatic number of a large graph is hard, so practical schedulers rely on methods that find good colorings rather than guaranteed best ones.

This content reflects the field as of October 2026.

Key Terms

• Conflict graph: A graph whose vertices are tasks or events and whose edges join pairs that can't happen at the same time.
• Graph coloring: Assigning colors to the vertices of a graph so that any two vertices joined by an edge get different colors.
• Chromatic number: The fewest colors needed to color a graph so that every edge joins two different colors.
• Approximation algorithm: A method that finds a solution with a guarantee of how far it can be from the best one.

References

• Chaitin, G. J. 1982. "Register Allocation & Spilling via Graph Coloring." In Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, 98–105. New York: Association for Computing Machinery. doi:10.1145/800230.806984.
  • Free: None confirmed
  • Publisher: ACM Digital Library
• Gonthier, Georges. 2008. "Formal Proof—The Four-Color Theorem." Notices of the American Mathematical Society 55 (11): 1382–1393.
  • Free: American Mathematical Society (PDF)
• Marx, Dániel. 2004. "Graph Colouring Problems and Their Applications in Scheduling." Periodica Polytechnica, Electrical Engineering 48 (1): 11–16.
  • Free: Periodica Polytechnica (PDF)

Introduction

Color a map so that no two neighboring countries share a color. However tangled the borders, four colors are always enough. Proving that took more than a century, and in the end it took a computer.

This reading covers the question and its history, the 1976 proof by Appel and Haken, why that proof was controversial, and the fully machine-checked proof completed in 2005.

A Question About Maps

The question first seems to have been raised by Francis Guthrie, who had studied under the mathematician Augustus De Morgan at University College London. In October 1852 the question reached De Morgan, who wrote to William Rowan Hamilton about it the same day (O'Connor and Robertson 1996b). Two regions count as neighbors if they share a stretch of border. Regions that meet only at a single point, like slices of a pie at its center, may share a color.

The answer took a long time. In 1879 Alfred Kempe announced a proof, which was published that year. In 1890 Percy John Heawood showed that Kempe's argument had a flaw, though he proved that five colors always suffice (O'Connor and Robertson 1996b). The question was open again.

Some maps need all four colors: a region surrounded by a ring of three neighbors that all touch each other, for example. Many maps need fewer. The four color theorem states that the regions of any flat map, each region a single connected piece, can be colored with at most four colors so that regions sharing a border get different colors (Gonthier 2008). It's a statement about graphs too. Make each region a vertex and join neighbors with an edge, and the theorem says such graphs never need more than four colors.

The 1976 Proof

Kenneth Appel and Wolfgang Haken's proof, announced in 1976, followed a strategy that went back to Kempe. They found a list of configurations, small patches of map, with two properties: every map must contain at least one of them, and none of them can appear in a smallest map that needs five colors. Together, those properties show that no map needs five colors.

The list had around 1,500 configurations, and checking the second property for each one by hand was out of the question. Appel and Haken used about 1,200 hours of computer time to work through the details (O'Connor and Robertson 1996b). In MacTutor's words, the four color theorem was "the first major theorem to be proved using a computer" (O'Connor and Robertson 1996b). It was a computer-assisted proof: a proof in which a computer carries out part of the argument, typically checking more cases than people could check by hand.

Why It Was Controversial

A proof is supposed to let a reader check every step. Appel and Haken's proof combined a written argument, which mathematicians could check by inspection, with computer code, which they couldn't (Gonthier 2008). To accept the result, you had to trust that the program did what its authors said.

Rerunning the program doesn't remove that worry. Gonthier notes that it can't catch the most common source of computer error: a mistake by the programmer (Gonthier 2008). Some mathematicians also wondered whether a proof no person could read in full explained why the theorem is true.

The controversy eased over time. A new proof by Robertson, Sanders, Seymour, and Thomas, published in the 1990s, used a smaller set of 633 configurations, but it still combined a written argument with computer code that couldn't be checked by hand (Gonthier 2008).

A Proof Checked by Machine

Georges Gonthier, working with Benjamin Werner, took a different route. They wrote the entire proof, both the reasoning and the case checking, in the language of Coq, a proof assistant: software that checks every logical step of a proof written in a precise formal language. Doing this meant making "every single logical step" explicit. They finished in 2005 (Gonthier 2008).

That makes the result an example of formal verification: checking by computer that every step of a proof follows, by the rules of logic, from stated axioms and results already proved. A formal proof can be checked by a separate program, so trust no longer rests on one team's code (Gonthier 2008).

Conclusion

The four color theorem is settled: four colors suffice for every flat map. Its history runs from a student's puzzle through a flawed proof, a contested computer-assisted proof, and a complete machine-checked one. Whether a proof that no person can read in full gives the same understanding as a traditional proof is still debated, even when its correctness is not.

This content reflects the field as of October 2026.

Key Terms

• Four color theorem: The theorem that the regions of any flat map, each region a single connected piece, can be colored with at most four colors so that regions sharing a border get different colors.
• Computer-assisted proof: A proof in which a computer carries out part of the argument, typically checking more cases than people could check by hand.
• Proof assistant: Software that checks every logical step of a proof written in a precise formal language.
• Formal verification: Checking by computer that every step of a proof follows, by the rules of logic, from stated axioms and results already proved.

References

• Gonthier, Georges. 2008. "Formal Proof—The Four-Color Theorem." Notices of the American Mathematical Society 55 (11): 1382–1393.
  • Free: American Mathematical Society (PDF)
• O'Connor, J. J., and E. F. Robertson. 1996b. "The Four Colour Theorem." MacTutor History of Mathematics Archive, University of St Andrews. Last updated September 1996.
  • Free: MacTutor: The Four Colour Theorem

Introduction

At any party of six people, there are always three who all know one another or three who are all strangers. That fact has a short proof. Ask the same question about groups of five, and the world's best mathematicians, with enormous computer searches, still can't give the answer.

This reading covers the party puzzle, what Ramsey numbers are, the current state of knowledge about the smallest unsolved case, and recent progress on large Ramsey numbers.

The Party Puzzle

Picture a party as a graph. Each guest is a vertex, a point, and every pair of guests is joined by an edge, a line. Color each edge red if the two guests are friends and blue if they're strangers.

A clique is a group of vertices in a graph in which every two are joined. In the party graph, a group of mutual friends is a red clique, and a group of mutual strangers is a blue clique.

Among any 6 guests, there is always a red or a blue clique of 3. The proof starts with one guest, uses the pigeonhole principle on that guest's five relationships, and finishes in two short cases. Five guests aren't enough: seat them in a circle, make neighbors friends and everyone else strangers, and no three are all friends or all strangers. The problem was posed in a 1953 Putnam competition for university students (Radziszowski 2026).

Ramsey Numbers

A Ramsey number is the smallest number of guests that guarantees either a group of a given size who are all friends or a group of a given size who are all strangers. Mathematicians write R(m, n), where m is the size of the friend group and n the size of the stranger group. The party puzzle says R(3,3) = 6.

Ramsey numbers always exist. However large the groups you ask for, some party size guarantees one of them. But knowing that a number exists is different from knowing its value. A value is pinned down with two kinds of argument:

• A lower bound is a number the true value is known to be at least, usually shown by exhibiting a party one guest smaller with no group of the required kind.
• An upper bound is a number the true value is known not to exceed, shown by a proof that covers every possible party of that size.

When the two meet, the number is known. The next case up was settled in 1955, when Greenwood and Gleason showed that R(4,4) = 18 (Radziszowski 2026).

The Smallest Open Case

The value of R(5,5) is unknown. In 1989 Exoo found a party of 42 guests with no five mutual friends and no five mutual strangers, so R(5,5) is at least 43 (Angeltveit and McKay 2026). No better lower bound has been found since.

The upper bound has come down slowly. In a paper first posted in 2024 and published in 2026, Vigleik Angeltveit and Brendan McKay lowered it from 48 to 46 (Angeltveit and McKay 2026). Their proof combined linear programming, a technique for optimizing under constraints, with computer checking of a very large number of cases. One author's computations took about 30 years of processor time, and the other author's independent check took about 50 more (Angeltveit and McKay 2026).

So R(5,5) is 43, 44, 45, or 46. Some researchers conjecture, with strong computational evidence, that it is 43 (Radziszowski 2026). The answer can't be found by brute force. A party of 43 guests has 903 pairs, and each pair can be red or blue, so there are 2^{903} ways to color the edges, a number with 272 digits.

Large Ramsey Numbers

For larger groups, exact values are hopeless, and the questions turn to how fast Ramsey numbers grow. In 1935 Erdős and Szekeres proved an upper bound for the diagonal case, where the friend and stranger groups are the same size. It stood, apart from smaller refinements, for almost 90 years.

In 2023 Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe posted a proof of the first exponential improvement on that bound, meaning an improvement that grows larger and larger relative to the old bound as the group size increases. It was published in 2026 (Campos et al. 2026).

Conclusion

Ramsey theory guarantees that large networks contain orderly patterns, but exact Ramsey numbers are known only for small cases. As of this writing, R(5,5) is known to lie between 43 and 46, and the question is open. Progress on large Ramsey numbers has come from new proof ideas rather than bigger searches.

This content reflects the field as of October 2026.

Key Terms

• Clique: A group of vertices in a graph in which every two are joined.
• Ramsey number: The smallest number of guests that guarantees either a group of a given size who are all friends or a group of a given size who are all strangers.
• Lower bound: A number the true value is known to be at least, usually shown by exhibiting a party one guest smaller with no group of the required kind.
• Upper bound: A number the true value is known not to exceed, shown by a proof that covers every possible party of that size.

References

• Angeltveit, Vigleik, and Brendan D. McKay. 2026. "R(5,5) ≤ 46." Journal of Graph Theory 112 (3): 198–208. doi:10.1002/jgt.70029. First posted as arXiv:2409.15709 (2024).
  • Free: arXiv 2409.15709
  • Publisher: Wiley Online Library
• Campos, Marcelo, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe. 2026. "An Exponential Improvement for Diagonal Ramsey." Annals of Mathematics 203 (3): 869–932. doi:10.4007/annals.2026.203.3.4. First posted as arXiv:2303.09521 (2023).
  • Free: arXiv 2303.09521
  • Publisher: Annals of Mathematics
• Radziszowski, Stanisław P. 2026. "Small Ramsey Numbers." Electronic Journal of Combinatorics, Dynamic Survey DS1.18. Revision 18, April 24, 2026.
  • Free: Rochester Institute of Technology (PDF)

Introduction

Among any six people, there are always three who are all friends with one another or three who are all strangers. That claim covers every possible group of six, and there are a great many of them. This walkthrough proves it in five steps, using nothing more than counting, and then shows why five people aren't enough.

The proof is the first case of Ramsey theory, the part of combinatorics that shows large enough structures must contain orderly patterns. It shows how such guarantees are proved: not by checking cases one at a time, but by an argument that covers them all at once.

The Starting Point

Six people are at a party. Every pair of them is either friends or strangers; there's no in-between, and the relationship goes both ways. Nothing else is known about who knows whom.

In graph terms, the six people are vertices, or points, and every pair of points is joined by an edge, or line. Color each edge red for friends and blue for strangers. Six people make 6 \times 5 \div 2 = 15 pairs, so there are 15 edges. Each edge can be either color, so the multiplication principle gives 2^{15} = 32{,}768 different parties.

The claim is that every one of those 32,768 parties contains a red triangle (three mutual friends) or a blue triangle (three mutual strangers). Mathematicians write this as R(3,3) \le 6: the Ramsey number for groups of three, the smallest party size that guarantees three mutual friends or three mutual strangers, is at most 6. The second half of the walkthrough shows that 5 people don't always contain such a triangle, so the Ramsey number is exactly 6. The question was posed in the 1953 Putnam competition for university students (Radziszowski 2026).

Walking Through the Proof

Step 1: Pick one person and look at their five relationships

Choose any one of the six people, and call them A. A has a relationship with each of the other five: five edges leave A, each red or blue.

The argument doesn't depend on which person you choose. Whatever is true for A will be true for anyone, so the proof covers every party without looking at any particular one.

Step 2: Use the pigeonhole principle to find three of the same kind

The pigeonhole principle says that if more items are placed into boxes than there are boxes, at least one box holds two or more. A stronger form says that if more than twice as many items as boxes are placed, some box holds at least three.

Here the items are A's five relationships, and the boxes are the two colors, friend and stranger. Five is more than twice two. So at least three of A's relationships are the same color. Two of each would account for only four; the fifth must make a third in one color.

Suppose, for now, that the three are friends. Call those three people B, C, and D. A is friends with each of them.

Step 3: If any two of those three are friends, you've found three mutual friends

Look at the relationships among B, C, and D. There are three of them: B and C, B and D, and C and D.

Suppose any one of those pairs is friends, say B and C. Then A, B, and C are three mutual friends: A is friends with B and with C (from Step 2), and B is friends with C. That's a red triangle, and the claim holds.

Step 4: If none of them are friends, those three are mutual strangers

The only other possibility is that no pair among B, C, and D is friends. Then all three pairs are strangers: B and C, B and D, and C and D. So B, C, and D are three mutual strangers, a blue triangle, and the claim holds again.

Steps 3 and 4 between them cover every case. Either some pair among B, C, and D is friends, or no pair is. There's no third option. So the party contains three mutual friends or three mutual strangers.

Step 5: Show that five people aren't enough

The proof used six people only once, in Step 2: A needed five relationships so that three were guaranteed to match. With five people, A has only four relationships, and two friends plus two strangers is possible. The proof breaks down. That suggests, but doesn't prove, that five might not be enough.

To prove it, you need a single party of five with no red triangle and no blue triangle. Seat five people around a round table. Make each person friends with the two people beside them and strangers with the two across the table.

Check for three mutual friends. Each person has only two friends, their two neighbors, and those two neighbors aren't seated beside each other, so they're strangers. No three people are all friends. Check for three mutual strangers. Each person's two strangers are the two people across the table, and those two sit next to each other, so they're friends. No three people are all strangers.

In graph terms, the friend edges form a five-sided ring, a pentagon, and the stranger edges form a five-pointed star inside it. Neither contains a triangle. So R(3,3) is greater than 5, and together with Steps 1 to 4, R(3,3) = 6.

Key Considerations

The argument works the same way if A's three matching relationships are strangers instead of friends. Swap the words "friends" and "strangers" everywhere in Steps 3 and 4: either two of the three are strangers, giving three mutual strangers with A, or none are, giving three mutual friends. Mathematicians often say "by symmetry" here, meaning the second case is the first with the colors exchanged.

The common mistake is thinking a single example proves the rule for all parties. Finding a party of six that contains three mutual friends shows nothing about the other 32,767. The proof never looks at a particular party; it works for any colors the 15 edges could have. The direction is reversed in Step 5, where a single example is exactly what's needed. To show that five people aren't always enough, one party without a triangle settles it.

The two halves of the result play different roles. Steps 1 to 4 give an upper bound, a number the true value can't exceed: R(3,3) is at most 6. Step 5 gives a lower bound, a number the true value is at least: R(3,3) is more than 5. When they meet, the value is known.

The same two-sided approach is used for larger cases, and that's where the difficulty lies. For groups of five, the best lower bound comes from a 42-person party with no five mutual friends or strangers, so R(5,5) is at least 43. The best upper bound is 46, proved with linear programming and years of computer checking (Angeltveit and McKay 2026). Closing that gap is an open problem.

Summary

Five steps prove that six people always contain three mutual friends or three mutual strangers, and one seating chart shows that five don't.

Pick any person, A. A has 5 relationships, each friend or stranger, so by the pigeonhole principle at least 3 are the same kind, say friends: B, C, and D.

Case 1: some pair among B, C, D are friends. With A, they form 3 mutual friends.

Case 2: no pair among B, C, D are friends. Then B, C, D are 3 mutual strangers.

If A's three are strangers, swap the words friends and strangers. Either way, the triangle exists, so R(3,3) \le 6.

Five people seated in a circle, friends with neighbors and strangers otherwise, contain neither 3 mutual friends nor 3 mutual strangers. So R(3,3) = 6.

1. The pigeonhole step is the only place the number 6 is used.
2. The two cases cover every possibility, which is why the argument holds for all 32,768 parties at once.
3. The five-person ring is a counterexample: one case is enough to show the guarantee fails.

References

• Angeltveit, Vigleik, and Brendan D. McKay. 2026. "R(5,5) ≤ 46." Journal of Graph Theory 112 (3): 198–208. doi:10.1002/jgt.70029. First posted as arXiv:2409.15709 (2024).
  • Free: arXiv 2409.15709
  • Publisher: Wiley Online Library
• Radziszowski, Stanisław P. 2026. "Small Ramsey Numbers." Electronic Journal of Combinatorics, Dynamic Survey DS1.18. Revision 18, April 24, 2026.
  • Free: Rochester Institute of Technology (PDF)