Rado graph
From Wikipedia, the free encyclopedia
The Rado graph, also known as the Random graph, is the unique (up to isomorphism) countable graph R such that for any finite graph G and any vertex a, any embedding of G − a into R can be extended to an embedding of G into R. As a result, the Rado graph 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.
- Deleting any finite number of vertices and/or edges from the Rado graph still yields the Rado graph, with all of its essential properties still intact.
[edit] References
- ^ Rado, R., Universal graphs and universal functions Acta Arith., 1964, 9, 331-340.
