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 !=∅, where ∅ denotes the empty set. This theorem is attributed by Erdős et al. (1966) to Szpilrajn-Marczewski. 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).

Erdős graph | intersection number