Talk:Rado graph

From Wikipedia, the free encyclopedia

This article currently starts

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.

This is not true. Consider the Rado graph together with an isolated vertex. Clearly this still has the desired property, but this graph is not isomorphic to the Rado graph (indeed, it violates the currently listed property "For any finite sets of vertices U and V, there exists a vertex connected to everything in U, and nothing in V." for U the set containing just the one isolated vertex). A correct statement would be something like

The Rado graph R is the unique countable graph with the property that for every finite graph G and any vertex a of G, each embedding of G - a into R can be extended to an embedding of G into R.

I will make this or a similar change now. Boris Alexeev (talk) 16:24, 23 December 2007 (UTC) Incidentally, insisting the graph be connected does not help either. Boris Alexeev (talk) 16:35, 23 December 2007 (UTC)