---
title: 'Why do all random graphs end up identical?'
source: 'https://youtube.com/watch?v=TNWl-0rle4A'
video_id: 'TNWl-0rle4A'
date: 2026-07-01
duration_sec: 1342
---

# Why do all random graphs end up identical?

> Source: [Why do all random graphs end up identical?](https://youtube.com/watch?v=TNWl-0rle4A)

## Summary

The video explores the surprising fact that all infinite random graphs, regardless of how they are generated (coin flips, dice rolls, or binary rules), converge to the same unique structure: the Rado graph. It explains the extension property, which is the key to proving both that the Rado graph contains every other graph as a subgraph and that any two such graphs are identical.

### Key Points

- **Random networks converge to identity** [0:00] — Two people drawing random networks by flipping coins will, if they continue indefinitely, end up with the identical network.
- **The Rado graph is inevitable** [2:45] — The Rado graph (named after Richard Rado) is the unique infinite random graph that all random graphs converge to.
- **Extension property defined** [7:14] — The extension property: for any two disjoint finite sets A and B, there exists a vertex connected to all in A and none in B.
- **Binary construction of Rado graph** [8:52] — The binary construction: label vertices with numbers; for two vertices, take the smaller number and check the binary digit of the larger at that position—1 means connect, 0 means don't.
- **Random graphs almost surely have extension property** [13:09] — For random graphs with nonzero edge probability, the probability that the extension property holds is 1 (almost sure).
- **Extension property implies universality** [14:13] — Using the extension property, you can build any finite graph vertex by vertex inside the Rado graph.
- **Uniqueness proof via matching** [16:20] — Two graphs with the extension property can be shown to be isomorphic by a back-and-forth matching argument.

## Transcript

Imagine you and a friend both want to draw a 
random network. I said and a friend. Come on  
in. Hey. Hey. How you doing? You know I do know 
because I'm you. Okay. Whenever you're ready.  
Look. Here's what you do. Okay. Both people draw 
a collection of vertices and then for every pair  
of vertices they flip a coin to decide whether 
or not to link those two vertices with an edge.  
Initially, the two networks look very different, 
but were these two close friends to carry on for a  
countably infinite number of vertices, they would 
end up drawing exactly the same network. And not  
just a network that seems similar, the identical 
network. This is the radioraph. Okay, plan two,  
folks. I want you both to draw a new random 
graph. that's different to the previous one. Now,  
my plan to make it different is instead of 
flipping a coin, I'm going to throw a dice  
like on two different axes to make it random. 
And if the top number is a six, which is not,  
I would then join the next two edges together, 
which means now there'll be far few edges. So,  
I just did that one. That's not going to be drawn. 
So, in theory, I should end up with not a six,  
a very different network. So my plan is I've 
numbered all the vertices and whenever I  
pair up two of them I'm going to get the smallest 
number and find that position in the other number  
in its binary representation and if it's a one I'm 
going to link them. If it's a zero I'm not. So the  
first position in two is a zero. So I don't link 
them. The first position in three is a one. So I'm  
going to link those. First position in four is a 
zero. Not linked. First position there is a one.  
So I link those. Now I do all the second 
positions. So the second position in Well,  
that's all well and good folks, but it turns 
out you are both once again drawing exactly the  
same network. Unbelievable. Yes, it turns out the 
radioraph is inevitable. Hey, caught it. Thanks.  
Even though random graphs may start off looking 
different, the longer you carry on making them,  
the more similar they become. And should you have 
infinitely many vertices in your random graph,  
it will always converge to be exactly the 
same. Yes, there is only one random graph.  
It's inevitable. But no matter what you do, 
you end up with the Rado graph named after  
mathematician Richard Rado or Rado. Anyway, people 
before Richard discovered this graph and people  
after him have and will continue to because it 
is inevitable. So I think of it as the rando  
graph and you won't hear graph theorists really 
talk about imagine a random graph. They will say  
imagine the random graph. There's only one and 
you can't avoid it. It's always there lurking  
behind you and it is the creator of all other 
graphs. Any graph you think of. So here we have  
the Peterson graph. Big fan. You can think of your 
own favorite graph. Somewhere in the RTO graph,  
this set of vertices exists exactly like this as 
a subgraph. And not just that one. Boom. Hersel  
graph that's in there too. Any finite or indeed 
countably infinite graph you can imagine is in  
there somewhere. It's inevitable and it contains 
all. If networks had a god, their deity would be  
the radioraph. And that could be it. That could 
be the end of the video. Crazy mass fact. Isn't  
that phenomenal? So if that's all you're here for, 
you can stop watching now. Although before you do,  
James 3 is sponsoring the video and I want you to 
know uh internship applications for the Hong Kong  
office are now open. I'll talk about more about 
it at the end of the video. I've been there.  
Wonderful office. You don't have to be in Hong 
Kong to apply. Details later on. But the point is,  
while we could end the video here, wouldn't it 
be more satisfying to prove all those things I  
just said? Because with one additional fact 
and a little bit of thinking it through,  
you can both convince yourself that the radioraph 
contains every other graph and you can convince  
yourself that it's inevitable. So, we're 
going to do it. That's inevitable. Okay. Now,  
it's just us people taking it seriously and we 
have to define some terms. I've been real fast and  
loose on calling things either networks or graphs. 
And that's because your average human would call  
a collection of nodes joined together by edges a 
network. Whereas mathematicians have decided we're  
going to call this a graph. So that's why I flip 
between them. Sometimes network makes more sense,  
but I want to use graph. So if you look things 
up afterwards, you've already got the correct  
um terminology. And we're talking a simple graph. 
So for any pair of vertices which is what we'll  
often call nodes because then if we call them 
vertices and edges the language is ready for  
making this equivalent to shapes like polyhedrrons 
anyway. So for this pair of vertices you either  
have them linked together or you don't. That's 
it. You can't have something like a double edge.  
I mean in other situations this is fine but in 
a simple graph no none of that and none of this  
going out from one vertex and coming back in. 
No none of that. For every pair there either is  
an edge or there is not an edge. And I've been 
referring to it being an infinite graph. What  
I strictly mean is a countably infinite graph of 
indistinguishable vertices. So that means first  
of all for every whole number all the countable 
numbers from one up to infinitely many there is a  
vertex for that. So there's more than seven there 
would be infinitely many of these with an exact  
correspondence to the counting numbers and they're 
indistinguishable. So while I have numbered these  
they're just temporary labels to help us keep 
track. There's nothing inherently for about  
that vertex. At any point we could re label them. 
The labels are just a convenience. Technically,  
you cannot distinguish between the vertices 
other than what edges there are and there  
are not. And that's just it. Um the board can 
can go away. Look at that magic. I'm using my  
foot. Uh so with that in mind, as long as you're 
happy with dealing with the notion of infinity,  
which can be a little annoying, but that's okay. 
Check out my video about infinitely many $1 bills,  
and you're okay following the logical steps of 
graph theory. There's no other prerequisites.  
We've got everything we need. We can prove these 
things. You can convince yourself everything I've  
said is true. We can achieve all of our hopes 
and dreams that pertain to this specific problem  
using a single property of an infinite graph. 
It's something called the extension property.  
And what the extension property means is you can 
take any collection of vertices you want from an  
infinite graph. And let's call them collection 
A. You can then take a second collection of any  
other vertices you want and call them collection 
B. And the only restriction is there cannot be a  
vertex that is in A and B. So you pick your own A 
and B arbitrary vertices as many or as few as you  
want. The extension property means that out 
there somewhere is at least one more vertex  
which is not in A or B and it has the interesting 
characteristic that it shares an edge in common  
with every single verticy in A but absolutely none 
of them in B. So you can pick any collection of  
vertices in A that you do want to all be connected 
to this new vertex and any vertices in B that you  
don't want to be connected and you're guaranteed 
to have at least one vertex which fulfills your  
wishes. And that's it. If we can show that a 
graph has the extension property, not only does  
that mean that it definitely contains every other 
graph as a subgraph somewhere, but it also means  
that any two graphs that both have the extension 
property are actually the same graph. We'll deal  
with the coin and the dice graphs in a moment, 
but first of all, we'll do the one where we use  
the binary digits to decide if we're going to link 
two edges or not. And here I've got my categories  
A and B and they're numbered. And again, the 
numbers are arbitrary. We've just numbered all  
the vertices in some order. Doesn't matter what. 
A quick recap on the binary method for edge rules.  
You have two vertices. You pick whichever one has 
the lowest albeit arbitrary number. That number  
will be our place position value. We then look at 
that place position in the binary version of the  
other vertex's bigger number. And if that position 
in the bigger number is one, then we join those  
two vertices together with an edge. And we don't 
if it isn't. And what I'm about to do next is show  
for these two sets, we can always find by a method 
of construction a vertex outside of them that  
fulfills the extension property requirements. And 
we look at all the numbers in here and we think,  
okay, there's going to be some other vertex out 
here, number n that links to these, but not those.  
So, first of all, we just guarantee n's going to 
be bigger than any of these. So, it's going to be  
bigger than six. Six has three digits in binary. 
So, long as this has more than three digits in  
binary, it's going to be bigger. And then we go 
through and we construct our number. You know  
what? I'm actually going to give it six digits in 
binary. And then we go through and we fill in the  
numbers to make it do what we want it to do. So we 
want it to link to one, so we put a one there. We  
want it to link to three and four, so one's there 
and there. We don't want it to link to two, so we  
put a zero there. We don't want it link to six, 
we put a zero there. And then the rest, whatever  
we want. So we happen to not care about the fifth 
one. I don't know. Uh, let's make that zero. Let's  
be a little bit lazy. which means now uh we've 
got the number 13. So it turns out n equals 13.  
Vertex number 13 if we were joining vertices up 
with that binary matching rule would fulfill our  
extension property requirements. And that would 
work for any set of numbered vertices in A and B.  
You could definitely find another numbered verticy 
which links to everything in A but nothing in B.  
and you're doing that by construction. The 
probability ones a little more hazy. Okay,  
for the coin flip graph, we're going to start with 
the same two categories of A and B. And then we're  
just going to pick some vertex out here somewhere. 
Let's uh say that's vertex, no, vertex I. There's  
a probability vertex I is the one we're after. 
There's a probability it's not. It's probably  
not you. We could say actually the probability 
of the vertex we're after not being I is equal  
to some value X and X is between zero and one. It 
can't equal one because there is a chance it's the  
one we're after. It's just probably not. So we'll 
look at another one. Here's a second vertex. We'll  
call that vertex J. There's a probability that's 
the one we're after. probably not the probability  
that it's not I or J equals X to the 2 now because 
we got two of them and the key thing here now is  
that X squ is going to be smaller than X because 
X is less than one so if we were to pick another  
vertex at random K and then check is it not I J 
or K we're now up to X cubed it's even smaller and  
if we had n different vertices that we've looked 
at the probability that we've not found the one  
we're after yet is x to the n. And as n approaches 
infinitely many, x to the n is going to approach  
zero. So the probability after we've checked 
infinitely many other vertices outside of a and  
b that we haven't found the one that we're after 
that satisfies the extension property is zero.  
So the probability that vertex does exist is one. 
It's almost certain, which is subtly different to  
guaranteed. I don't want to get into probability 
like measure theory stuff. There's always like  
some malicious graph like what if there were 
no edges at all? I don't care about that. The  
point is if you've got infinitely many vertices 
that are joined together randomly, it is almost  
certain with probability one that the extension 
property holds. And we haven't picked a value for  
x that's anything between zero and one. So this 
logic holds for coin flips. It holds for rolling  
a dice. As long as there's a nonzero chance you've 
linked any given pair of vertices together, you  
will have the extension property almost certainly 
with probability one. And who can ask for more  
than that? The point is all random graphs converge 
on the rattle graph with the extension property.  
We now know that all our graphs have the extension 
property. And we'll deal with proving that they're  
all the same graph in a moment. It's easier to 
first of all prove that the extension property  
implies all other graphs are subgraphs. So as 
an example here, I have a nice friendly small  
graph. I have the diamond graph and I've 
numbered the vertices 1 to four. Again,  
that's arbitrary. You can number them however you 
want. We're going to prove that this indeed any  
other graph is somewhere in the radar. And we do 
that by building it up one vertex at a time. So  
the lowest numbered vertex one, just pick a vertex 
that's going to be our corresponding number one.  
Then to fill in the second vertex, we work out 
what we need it connected to. So we've already got  
one. So we do want it connected to one. So we're 
going to call that category A. And we don't want  
it connected to well, we haven't got anything else 
yet. So strictly speaking, B would be a null, some  
kind of null set over here somewhere. Uh that is 
just completely empty. We don't care. And we know  
by the extension property, we can definitely find 
a vertex that's connected to everything in A and  
nothing in B. So now we've got two. Now three has 
to be connected to both of the previous ones we've  
already got. So now we redefine A to not just be 
one but to be one and two at the same time. And  
B is still the empty category. And we know by the 
extension property we can definitely find a vertex  
three add it to the graph and then we just keep 
going. Each time we want to add one more vertex  
we define our categories A and B to force that 
verticy to exist. And we know by the extension  
property it will. So four four has to be connected 
to two and three but not one. Give me a second.
All right. I've defined three and four to be in 
A and one to be in B. So we know by the extension  
property we can find a vertex that's exactly 
the same as what we want for our four links  
to both of these but not that one. And then we 
just keep going for each new vertex. Redefine A  
and B. It guarantees we can find the next vertex 
down. Fill it in. Repeat over and over and over.  
As long as we have the extension property, we 
can build up any graph we want of any size of  
our choosing. Finally, I have two infinite graphs 
that are generated however you want. Coin flips,  
binary, your choice. The point is they both have 
the extension property. And we're going to prove  
they're exactly the same graph. And we're going 
to do that by gradually putting each of them into  
a region within the graph. And we'll keep the 
two regions identical until they cover all of  
both of the graphs, showing that the whole graphs 
are identical. Okay, just bear with me. Here's  
how we're going to do it. First of all, we'll use 
the lowest numbered vertex in each of the graphs.  
Doesn't matter how you number them. Just assign a 
whole number to every single vertex and put vertex  
one and vertex one in a region. Doesn't matter 
which because they're not joined to anything  
else in the region. We're now on the first graph 
going to move in the second lowest numbered vertex  
which may or may not be connected to the first 
one. In this case it is and we have to do the  
same thing on this side. So using the extension 
property we find another vertex that is connected  
to the first one may not be the second one and we 
move that in. We then pick the next lowest number  
vertex outside the region in this graph. Check 
how it's connected to all the ones already in  
the region. Move it in. And at the same time, 
use the extension property to find a matching  
one over here and move it in as well. And then 
find the next lowest on this side. Move it in.  
Find the matching one. Move it in. And then we 
go backwards and forwards. And because each time,  
whichever one we move in on one, we can find a 
matching one using the extension property in the  
other one. And because we're going backwards and 
forwards, we're not leaving any unmatched. We will  
gradually match up all the vertices in both of 
these infinite graphs into pairs where each pair  
are identical vertices. And that's it. That's 
we can do that and we can prove both graphs are  
identical. Now again, this does in involve not 
getting too stressed out about infinity and  
these kind of matching things up. But if you've 
done stuff involving, you know, Hilbert's hotel  
and and matching stuff with countably infinite 
sets, you're already you you'll recognize this  
this kind of matching approach. But it does work. 
As long as you're systematic, you can prove these  
are exactly the same graph. All infinite random 
graphs are the radraph. There's only one. So  
that is the rando graph. And isn't it satisfying 
that we actually went through the explanation,  
the logic, the proof, and we took what were 
counterintuitive weird properties and eventually  
made them well almost obvious. In fact, the longer 
you think about it, the more obvious they get. And  
the whole extension property is just kind of 
codifying obviousness. I mean, it's my theory.  
Any sufficiently well-explained mathematics is 
indistinguishable from being obvious. for some  
in some cases a lot of explanation. But the point 
is understanding things is its own joy. And if you  
enjoy learning things, oh, here comes a segue for 
you cuz this video is sponsored by Jane Street and  
they have opened their internships in their Hong 
Kong office. Yes, they do also have internships  
available in their New York and London offices, 
but they're specifically recruiting for curious,  
enthusiastic individuals to join the team in Hong 
Kong. Jane Street are a quantitive trading firm  
who use techniques from machine learning, 
distributed systems, programmable hardware,  
and of course, statistics to trade on markets all 
around the world. And they're currently accepting  
applications for internships in quantitive 
trading, software engineering, research,  
institutional sales, and naturally trading. This 
one-of-a-kind internship experience runs from  
May until August in 2026. And during that time, 
you'll be surrounded by brilliant people from a  
diverse range of backgrounds and cultures who are 
passionate about what they do and eager to teach  
you what they know. And when you're not working, 
you get to enjoy Jane Street's fantastic office in  
Hong Kong, join in the social events, and watch 
the guest speakers, which this year included  
me. I try to go out to Hong Kong as often as I 
can. I was there to see the most recent fleet,  
actually the most recent two groups of interns in 
Hong Kong. I gave a talk. I got to hang out. Uh,  
we ate pizza. We talked about maths. We had a 
great Well, I had a great time. I think everyone  
else had a great time. Anyway, I always enjoy 
visiting the Jane Street office in Hong Kong. It's  
such a phenomenal city, and you'll get to enjoy 
living in Hong Kong while also hanging out with  
a group of like-minded people. All the details are 
in the description below or use the QR code on the  
screen right now. But spoiler, here are some 
things you don't need. You don't need to have  
a background in finance. A lot of Jane Streeters 
were like you, no finance experience. They did the  
internship to find out what it would be like to 
work in the quantitive trading industry. And you  
don't have to be in Hong Kong already. Jane Street 
will fly you there. In fact, you don't have to  
already have a pile of money because Jane Street 
will cover your travel and accommodation to Hong  
Kong and they will pay you a salary. It's a paid 
internship for your time there over the summer.  
If you have a curious mind and a collaborative 
spirit, you will fit right in at Jane Street.  
Please do check out the details or pass them on to 
someone who you think would benefit from them. And  
huge thanks to Jane Street for sponsoring this 
video. Well, that's it. Thank you so much for  
watching the video. But before we go, for one last 
time, here comes the whiteboard again. Like magic.  
How's that even happening? Huh? It was me. That 
was me the whole time. Yeah. Yeah. And while we're  
here, if you have watched right to the end of this 
video, I mean, thanks. It's been a wonderful year.  
Next year, calculating pie on the moon. Yeah. 
And before the year is over, you can still sign  
up for a digital Christmas card from me. Yes, 
it's too late for us to post a physical card.  
If you do sign up, uh we will email one to you. 
So that's it from me and me. Thanks for watching.