*(This is a follow-up to my previous questions [Natural models of graphs?](https://mathoverflow.net/questions/11647/natural-models-of-graphs).)*


Erdös in [The Representation of a Graph by Set Intersections](http://www.renyi.hu/~p_erdos/1966-21.pdf) (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](http://en.wikipedia.org/wiki/Arithmetic_progression). 


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](http://en.wikipedia.org/wiki/Green%25E2%2580%2593Tao_theorem) 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?


**Added**: Due to Kevin's concise answer and Thomas' comment, I'd like to add the following question:



> 
> **Question:** If not every graph on $k$ nodes can 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$: **Are there interesting classes of graphs with this property?**
> 
> 
> 



Can every finite graph be represented by an arithmetic sequence of natural numbers?
OK so take the unique tree on 3 vertices. Claim: you can't encode this with an arithmetic progression (AP). For if the AP is $a,a+d,a+2d$ then (because we have two edges) either vertices 1 and 2 are joined, or vertices 2 and 3 are joined (or both). Hence there is some $p>1$ such that either $p$ divides both $a$ and $a+d$, or $p$ divides both $a+d$ and $a+2d$. In either case, $p$ then divides $d$, so it divides $a$, so it divides everything, so the graph is complete.


