Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers

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

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 $nleq $ 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⁽¹⁾⁽²⁾, 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?

---

⁽¹⁾ 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

⁽²⁾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