Papalocal
Loading…
Papalocal · Things
Work

Rado graph

Rado graph is an infinite graph containing all countable graphs. It is based on set of non-negative integers.

All 6 facts, and where they come from

Facts

6 facts · 0 confirmed by two sources · 0 cited · 6 from one source

What it is
undirected graph One source
symmetric graph One source
infinite graph One source
Based on
set of non-negative integers One source
Named after
Richard Rado One source
Paul Erdős One source

Where this comes from

Papalocal keeps its own record. It started from these sources; what each one said is kept here as it was copied, so a change on their side never changes this page by itself. Tap one to read its version.

What Wikidata says · copied November 19, 2026 · revision 2263330698
Described as
infinite graph containing all countable graphs
Other names
Erdős–Rényi graph
What it is
undirected graph; symmetric graph; infinite graph
Based on
set of non-negative integers
Named after
Richard Rado; Paul Erdős
Wikipedias with a page
6

Wikidata item Q7281501 (wikidata.org/wiki/Q7281501), public domain (CC0). Copied 2026-11-19.

What Wikipedia says · copied November 19, 2026 · revision 1386533388

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, as a graph whose vertices are hereditarily finite sets (finite sets whose elements are hereditarily finite) with edges representing set membership, as a graph whose vertices are natural numbers and whose edges are given by the BIT predicate that uses the smaller of two numbers as an index into the binary representation of the other number, or as a graph of certain prime numbers that are connected by edges when one number is a square modulo another.
Every finite or countably infinite graph is an induced subgraph of the Rado graph, and can be found as an induced subgraph by a greedy algorithm that builds up the subgraph one vertex at a time. The Rado graph is uniquely defined, among countable graphs, by an extension property that guarantees the correctness of this algorithm: no matter which vertices have already been chosen to form part of the induced subgraph, and no matter what pattern of adjacencies is needed to extend the subgraph by one more vertex, there will always exist another vertex with that pattern of adjacencies that the greedy algorithm can choose.
The Rado graph is highly symmetric: any isomorphism of its finite induced subgraphs can be extended to a symmetry of the whole graph.
The first-order logic sentences that are true of the Rado graph are also true of almost all random finite graphs, and the sentences that are false for the Rado graph are also false for almost all finite graphs. In model theory, the Rado graph is an example of the unique countable model of an ω-categorical theory.

From the Wikipedia article “Rado graph” (en.wikipedia.org/wiki/Rado_graph), by its contributors, under CC BY-SA 4.0 (creativecommons.org/licenses/by-sa/4.0/). Copied 2026-11-19; not changed.

Confirmed Two sources agree. Cited One source, and it names where it got it. One source One source, without a reference of its own. Sources disagree The sources disagree. We show the best-supported value and keep theirs below.

Picture: Wikimedia Commons: Rado graph.svg · See Commons file page

People connected 1

Known for it