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. Note that this use of "Erdős sequence" is distinct from graphic sequences associated with Erdős and Gallai.
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 graph  | (6, 10, 14, 15, 21) |
