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], [2], [3], [4])

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

DEFINITIONA natural number $d$ may be called

demi-primeiff 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

CONJECTUREFor 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)$ arecoprime.

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,487^{th} 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

QUESTIONHas 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
```

mildly exhaustive:P $\endgroup$ – Mariano Suárez-Álvarez Mar 23 '10 at 2:11