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.

Čulik, K. "Applications of Graph Theory to Mathematical Logic and Linguistics." Proc. Symp. Graph Theory, Smolenice, 13-20, 1963.Erdős,
P.; Goodman, A. W.; and Pósa, L. "The Representation of a Graph
by Set Intersections." Canad. J. Math.18, 106-112, 1966.Szpilrajn-Marczewski,
E. "Sur deux propriétes des classes dÕensembles." Fund.
Math.33, 303-307, 1945.