Erdős Sequence

Let G be an arbitrary graph. Then there is a set S and a family of subsets S_1, S_2, ... of S which can be put in one-to-one correspondence with the vertices of G in such a way that edges of G occur iff S_i!=S_j and S_i union S_j!=emptyset, where emptyset 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 G on n vertices, there exists a sequence of n distinct nonnegative integers (v_1,v_2,...,v_n) that can be put into one-to-one correspondence with the vertices of G in such a way that vertices v_i and v_j are joined by an edge iff i!=j and (i,j) 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 n>2 vertices is given by p_(n-1)#, where p_k denotes a primorial. This value is achieved by star graphs S_n for n>2.

Simple cases include the empty graph K^__n, which has the sequence (1,2,3,...,p_(n-1)), where p_k is the kth prime, and the complete graph K_n, which has the sequence (2,4,6,...,2n).


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.

graphErdős sequence
empty graph K^__2(1, 2)
path graph P_2(2, 4)
empty graph K^__3(1, 2, 3)
path graph P_3(2, 3, 6)
triangle graph C_3(2, 4, 6)
claw graph K_(1,3)(2, 3, 5, 30)
tetrahedral graph K_4(2, 4, 6, 8)
path graph P_4(3, 5, 6, 10)
square graph C_4(10, 14, 15, 21)
star graph S_5(2, 3, 5, 7, 210)
wheel gaph W_5(6, 10, 14, 15, 21)

See also

Erdős Graph, Intersection Number

Explore with Wolfram|Alpha


Č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.

Cite this as:

Weisstein, Eric W. "Erdős Sequence." From MathWorld--A Wolfram Web Resource.

Subject classifications