*(This is a follow-up to my previous questions [Natural models of graphs?][1].)*

Erdös in [The Representation of a Graph by Set Intersections][2] (1966) states:

> **Theorem**. 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 into one-to-one
> correspondence with the vertices of
> $G$ in such a way that $x_i$ and $x_j$ are joined by an
> edge of $G$ iff $i \neq j$
> and $S_i \cap S_j \neq \emptyset$.

If we identify $S$ with a set of prime numbers and each $S_i$ with the product of its members we get the following:

> **Corollary**. Let $G$ be an arbitrary finite
> graph. Then there is a sequence of natural numbers $(n_1, n_2, ..., n_k)$ 
> which can be put into one-to-one
> correspondence with the vertices of
> $G$ in such a way that  $x_i$ and $x_j$ are joined by an edge iff $i \neq j$ and GCD$(n_i, n_j) > 1$.

We can choose the prime numbers (the elements of $S$, from which the $n_i$ are built) arbitrarily, and so the question arises, whether they can always be choosen in such a way, that the set $(n_1, n_2, ..., n_k)$ is an [arithmetic sequence][3]. 

Of course every *complete* graph on $k$ nodes can be represented by an arithmetic sequence: just take some consecutive sequence of even numbers. [Green-Tao's Theorem][4] guarantees that also every *empty* graph on $k$ nodes can be represented by an arithmetic sequence $(p_1, p_2, ..., p_k)$ of primes.

> **Question:** Can every graph on $k$ nodes be represented by an arithmetic sequence
> of natural numbers such that  $n_i$ and $n_j$ are joined by an edge iff $n_i \neq n_j$ and GCD$(n_i, n_j) > 1$

This would be one kind of *natural model of a graph*, that I was looking for, originally.

Maybe some references?


  [1]: http://mathoverflow.net/questions/11647/natural-models-of-graphs
  [2]: http://www.renyi.hu/~p_erdos/1966-21.pdf
  [3]: http://en.wikipedia.org/wiki/Arithmetic_progression
  [4]: http://en.wikipedia.org/wiki/Green%25E2%2580%2593Tao_theorem