Let be an arbitrary graph. Then there is a set and a family of subsets , , ... of which can be put in one-to-one correspondence with the vertices of in such a way that edges of occur iff and , where denotes the empty set. This theorem is attributed by Erdős et al. (1966) to Szpilrajn-Marczewski (1945).
A corollary of this theorem is that for every finite simple graph on vertices, there exists a sequence of distinct nonnegative integers that can be put into one-to-one correspondence with the vertices of in such a way that vertices and are joined by an edge iff and are not relatively prime (i.e., if they share a common factor).
Such a sequence may be termed an Erdős sequence, and the graph corresponding a given Erdős sequence an Erdős graph, terms perhaps introduced here for the first time.
For example, the Erdős sequence (2, 3, 5, 6, 10, 15) corresponds to the 2-triangular grid graph, as illustrated above.
The smallest maximum value in an Erdős sequence on a graph with vertices is given by , where denotes a primorial. This value is achieved by star graphs for .
Simple cases include the empty graph , which has the sequence , where is the th prime, and the complete graph , which has the sequence .
The following table summarizes the Erdős sequences of various graphs that the the lexicographically first having smallest possible maximum value. They are also illustrated above.
graph | Erdős sequence |
empty graph | (1, 2) |
path graph | (2, 4) |
empty graph | (1, 2, 3) |
path graph | (2, 3, 6) |
triangle graph | (2, 4, 6) |
claw graph | (2, 3, 5, 30) |
tetrahedral graph | (2, 4, 6, 8) |
path graph | (3, 5, 6, 10) |
square graph | (10, 14, 15, 21) |
star graph | (2, 3, 5, 7, 210) |
wheel gaph | (6, 10, 14, 15, 21) |