Rado graph

From Wikipedia, the free encyclopedia

The Rado graph, also known as the Random graph, is the unique countably infinite graph that contains all countable (finite and infinite) graphs as induced subgraphs.

[edit] History

The Rado graph was introduced by Richard Rado in 1964 ^[1].

[edit] Properties

• Every finite graph is an induced subgraph of the Rado graph.
• Every countably infinite graph is an induced subgraph of the Rado graph.
• Ultrahomogeneous (given any two isomorphic induced subgraphs of the Rado graph, every isomorphism between them extends to an automorphism on the entire graph).
• For any finite sets of vertices U and V, there exists a vertex connected to everything in U, and nothing in V.

[edit] References

1. ^ Rado, R., Universal graphs and universal functions Acta Arith., 1964, 9, 331-340.