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 are 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) |
