<p>From the comment: in the mathematical field of graph theory, the <a href="http://en.wikipedia.org/wiki/Rado_graph" rel="nofollow">Rado graph</a> [1], also known as the random graph or the Erdős–Rényi graph, is the unique (up to isomorphism) countable graph $R$ such that for every finite graph $G$ and every vertex $v$ of $G$, every embedding of $G − v$ as an induced subgraph of $R$ can be extended to an embedding of $G$ into $R$. As a result, the Rado graph contains all finite and countably infinite graphs as induced subgraphs.</p>

<p>In <a href="http://www.math.brown.edu/~res/MathNotes/random.pdf" rel="nofollow">this note</a> you can find other details, in particular: ... if we produce two random infinite graphs, then, with probability 1, they both have the extension property. Hence they are isomorphic (and also isomorphic to the Rado graph); in other words, any two random countably infinite graphs are isomorphic ... </p>

<p>[1] Rado, Richard (1964), "<a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa9/aa9133.pdf" rel="nofollow">Universal graphs and universal functions</a>", Acta Arith. 9: 331–340.</p>

CC BY-SA 3.0
2014-04-04T12:24:07.150Z
2014-04-04T12:35:47.890Z
2014-04-04T12:35:47.890Z
Marzio De Biasi
<p>I once skimmed a paper which examined the probability of two (infinite) graphs picked at random being isomorph. The surprising result was that for two random infinite graphs this probability is quite high as opposed to the finite case. I remember it being referenced in the context of why so many graph invariants  - often claimed to be complete - work correct on most inputs.</p>

<p>I think the paper was published before the nineties.</p>

CC BY-SA 3.0
2014-04-03T12:22:49.243Z
Do you mean the [Rado graph](http://en.wikipedia.org/wiki/Rado_graph) (which is unique up to isomorphisms) and the fact that generating two infinite *normal*  random graphs, with probability 1 they are isomorphic (and isomorphic to the Rado graph)? (see for example [this note](http://www.math.brown.edu/~res/MathNotes/random.pdf) )
Marzio De Biasi
CC BY-SA 3.0
2014-04-04T10:59:27.760Z
@MarzioDeBiasi yes, that is the result I'm talking about. Oddly, I cannot find the paper I had in mind.. maybe I mixed something up. 

However, this paper [Random graph isomorphism](http://www.renyi.mta.hu/~p_erdos/1980-35.pdf) supports my claim as to why many graph invariants work correctly in most cases.

Post your comment as answer and I'll accept it.
John D.
<reference-request><graph-isomorphism>
Probability of random (in)finite graphs being isomorphic
John D.
# Probability of random (in)finite graphs being isomorphic

(Asked by: username_0 on 2014-04-03)

I once skimmed a paper which examined the probability of two (infinite) graphs picked at random being isomorph. The surprising result was that for two random infinite graphs this probability is quite high as opposed to the finite case. I remember it being referenced in the context of why so many graph invariants - often claimed to be complete - work correct on most inputs.

I think the paper was published before the nineties.

**Tags:** reference-request, graph-isomorphism

> **Comments:**
> **username_1**: Do you mean the [Rado graph](http://en.wikipedia.org/wiki/Rado_graph) (which is unique up to isomorphisms) and the fact that generating two infinite *normal*  random graphs, with probability 1 they are isomorphic (and isomorphic to the Rado graph)? (see for example [this note](http://www.math.brown.edu/~res/MathNotes/random.pdf) )  
> **username_0**: @MarzioDeBiasi yes, that is the result I'm talking about. Oddly, I cannot find the paper I had in mind.. maybe I mixed something up.   However, this paper [Random graph isomorphism](http://www.renyi.mta.hu/~p_erdos/1980-35.pdf) supports my claim as to why many graph invariants work correctly in most cases.  Post your comment as answer and I'll accept it.  

---

## 1 answers

### Answer by username_1 on 2014-04-04. Score: 3 | Accepted answer

From the comment: in the mathematical field of graph theory, the [Rado graph](http://en.wikipedia.org/wiki/Rado_graph) [1], also known as the random graph or the Erdős–Rényi graph, is the unique (up to isomorphism) countable graph $R$ such that for every finite graph $G$ and every vertex $v$ of $G$, every embedding of $G − v$ as an induced subgraph of $R$ can be extended to an embedding of $G$ into $R$. As a result, the Rado graph contains all finite and countably infinite graphs as induced subgraphs.

In [this note](http://www.math.brown.edu/~res/MathNotes/random.pdf) you can find other details, in particular: ... if we produce two random infinite graphs, then, with probability 1, they both have the extension property. Hence they are isomorphic (and also isomorphic to the Rado graph); in other words, any two random countably infinite graphs are isomorphic ...

[1] Rado, Richard (1964), "[Universal graphs and universal functions](http://matwbn.icm.edu.pl/ksiazki/aa/aa9/aa9133.pdf)", Acta Arith. 9: 331–340.


---

