Some MOers have been skeptic whether something like *natural number graphs* can be defined coherently such that every finite graph is isomorphic to such a graph. (See my previous questions [[1](https://mathoverflow.net/questions/17989/can-every-finite-graph-be-represented-by-one-prescribed-sequence-of-natural-numbe)], [[2](https://mathoverflow.net/questions/17875/can-every-finite-graph-be-represented-by-an-arithmetic-sequence-of-natural-number)], [[3](https://mathoverflow.net/questions/18562/uniformly-computable-classes-of-graphs)], [[4](https://mathoverflow.net/questions/11647/natural-models-of-graphs)])


Without attempting to give a general definition of *natural number graphs*, I invite you to consider the following



> 
> **DEFINITION**
> 
> 
> A natural number $d$ may be called **demi-prime**
>  iff there is a prime number $p$ such
>  that $d = (p+1)/2$. The demi-primes' distribution is exactly
>  like the primes, only shrinked by the
>  factor $2$:
> 
> 
> $$2, 3, 4, 6, 7, 9, 10, 12, 15, 16, 19, 21, 22, 24, 27, 30, 31, 34, 36, 37, 40, 42, 45, 49, ...$$
> 
> 
> Let **D**($k,n$) be the set which consists
>  of the $k$-th up to the $(k+n-1)$-th
>  demi-prime number. 
> 
> 
> 


After some - mildly exhaustive - calculations I feel quite confident to make the following



> 
> **CONJECTURE**
> 
> 
> For every finite graph $G$ there is a $k$ and a bijection $d$ from the vertex set
>  $V(G)$ to **D**($k,|G|$) such that $x,y$ are adjacent if and only if $d(x),d(y)$ are **coprime**.
> 
> 
> 


I managed to show this rigorously for all graphs of order $n\leq $ 5 by brut force calculation, having to take into account all (demi-)primes $d$ up to the 1,265,487th one for graphs of order 5. For graphs of order 4, the first 1,233 primes did suffice, for graphs of order 3 the first 18 ones. 


Looking at some generated statistics for $n \leq$ 9 reveals interesting facts(1)(2), correlations, and lack of correlations, and let it seem probable (at least to me) that the above conjecture also holds for graphs of order $n >$ 5. 


Having boiled down my initial intuition to a concrete predicate, I would like to pose the following



> 
> **QUESTION**
> 
> 
> Has anyone a clue how to prove or disprove the above conjecture?
> 
> 
> 


My impression is that the question is about the randomness of prime numbers: Are they distributed and their corresponding demi-primes composed randomly enough to mimick – via **D**($k,n$) and coprimeness – all (random) graphs? 




---


(1) E.g., there is one graph of order 5 - quite unimpressive in graph theoretic terms - that is very hard to find compared to all the others: it takes 1,265,487 primes to find this guy, opposed to only 21,239 primes for the second hardest one. (Lesson learned: Never stop searching too early!) It's – to whom it is of interest – $K\_2 \cup K\_3$:



```
0 1 0 0 0
1 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0

```

(2) **Added:** This table shows the position of the smallest prime (among all primes) needed to mimick the named graphs of order $n$. All values not shown are greater than $\approx 2,000,000$



```
order    |   3     4      5      6       7      8
-------------------------------------------------
empty    |  14    45     89     89      89   3874 
complete |   5    64    336   1040   10864  96515 
path     |   1     6   3063  21814  
cycle    |   5   112  21235  49957 

```


Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers
**Theorem:** Schinzel's hypothesis H implies the conjecture. 


**Proof:** Choose distinct primes $q\_S > 100|G|$ indexed by the 2-element subsets $S$ of $G$. For each $i \in G$, let $Q\_i$ be the set of $q\_S$ for $S$ such that $i \in S$ and the edge $S$ is not part of $G$. Let $P\_i$ be the product of the primes in $Q\_i$. Let $P = 4 \prod\_S q\_S^2$.


By the Chinese remainder theorem, for each $i$ we can find a positive integer $a\_i$ such that 


$a\_i \equiv 1 \bmod{\ell^2}$ for each prime $\ell \le 10|G|$,


$a\_i \equiv q-1 \bmod{q^2}$ for each $q \in Q\_i$, and 


$a\_i \equiv 1 \bmod{q\_S}$ for each $q\_S \notin Q\_i$. 


Moreover, we can choose the $a\_i$ to be distinct. Let $J$ be the set of positive integers up to $\operatorname{max} a\_i$, but excluding all of the $a$'s themselves (i.e., $J$ consists of the numbers in the gaps). For each $j \in J$ choose a prime $s\_j$ much larger than all the $a\_i$ and all the $q\_S$.


Consider the linear polynomials $P n + a\_i$ and $(P n + a\_i + 1)/(2P\_i)$ In $\mathbf{Z}[n]$. For each prime $\ell \le 10|G|$ and each $\ell$ of the form $q\_S$, all these $2|G|$ polynomials are nonzero mod $\ell$ at $n=0$. For each other prime $\ell$, there exists $n$ such that all these polynomials are nonzero mod $\ell$, since $n$ needs to avoid no more than $2|G|$ residue classes mod $\ell$. Furthermore, we can impose the condition that $P n+j$ is divisible by $s\_j^2$ for each $j \in J$, and still find $n$ as above. Therefore Schinzel's hypothesis H implies that there exist arbitrarily large positive integers $n$ such that the numbers $P n+a\_i$ and $(P n + a\_i + 1)/(2P\_i)$ are all prime, and such that $P n+j$ is not prime for $j \in J$. This makes the numbers $p\_i:=P n + a\_i$ *consecutive* primes such that $(p\_i+1)/2 = P\_i r\_i$ for some prime $r\_i$. If $n$ is sufficiently large, then these primes $r\_i$ are all distinct and larger than all of the $q\_S$. So the greatest common factor of $(p\_i+1)/2$ and $(p\_j+1)/2$ for $i \ne j$ equals $1$ if there is an edge between $i$ and $j$, and $q\_{\{i,j\}}$ otherwise. $\square$




---


**Remark:** Given how little is known about consecutive primes, it seems unlikely that the conjecture can be proved unconditionally. But at least now we can be confident that it's true!


