3 Completely new answer, conditional on Schinzel

The conjecture is true if you don't insist that

Theorem: Schinzel's hypothesis H implies the demi-primes are consecutiveconjecture.

Proof: Choose distinct large primes $q_S$ q_S > 100|G|$indexed by the 2-element subsets$S$of$G$. It suffices to construct odd primes$p_x$for For each$x i \in G$such that 1) , let$p_x$is not equal to Q_i$ be the set of $q_S$ for any $x$ and $S$

2) $(p_x+1)/2$ is divisible by $q_S$ if and only if such that $x i \in S$ and the edge $S$ is not part of $G$, and

3) for distinct G$. Let$x$and P_i$ be the product of the primes in $y$, Q_i$. Let$P = 4 \prod_S q_S^2$. By the numbers Chinese remainder theorem, for each$(p_x+1)/2$and i$ we can find a positive integer $(p_y+1)/2$ have no common a_i$such that$a_i \equiv 1 \bmod{\ell^2}$for each prime factors except$\ell \le 10|G|$,$a_i \equiv q-1 \bmod{q^2}$for possibly the each$q_S$. In factq \in Q_i$, this is easy: just and

$a_i \equiv 1 \bmod{q_S}$ for each $q_S \notin Q_i$.

Moreover, we can choose the $p_x$ one at a timea_i$to be distinct. The conditions imposed on any one Let$p_x$by 2) and 3) amount J$ be the set of positive integers up to finitely many congruence conditions with prime moduli$\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 modulus appears at most once, $\ell \le 10|G|$ and none each $\ell$ of the form $q_S$, all these $2|G|$ polynomials are asking nonzero mod $p_x$ \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 be 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 modulusnumbers$P n+a_i$and$(P n + a_i + 1)/(2P_i)$are all prime, so they 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 satisfiable by Dirichlet's theorem on 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 primesin arithmetic progressions, it seems unlikely that the conjecture can be proved unconditionally. But at least now we can be confident that it's true! 2 OK, he wants consecutive demi-primes The conjecture is true if you don't insist that the demi-primes are consecutive. Choose distinct large primes$q_S$indexed by the 2-element subsets$S$of$G$. It suffices to construct odd primes$p_x$for$x \in G$such that 1)$p_x$is not equal to$q_S$for any$x$and$S$2)$(p_x+1)/2$is divisible by$q_S$if and only if$x \in S$and the edge$S$is not part of$G$, and 3) for distinct$x$and$y$, the numbers$(p_x+1)/2$and$(p_y+1)/2$have no common prime factors except for possibly the$q_S$. In fact, this is easy: just choose the$p_x$one at a time. The conditions imposed on any one$p_x$by 2) and 3) amount to finitely many congruence conditions with prime moduli, and each prime modulus appears at most once, and none are asking$p_x$to be divisible by the modulus, so they are satisfiable by Dirichlet's theorem on primes in arithmetic progressions. 1 The conjecture is true. Choose distinct large primes$q_S$indexed by the 2-element subsets$S$of$G$. It suffices to construct odd primes$p_x$for$x \in G$such that 1)$p_x$is not equal to$q_S$for any$x$and$S$2)$(p_x+1)/2$is divisible by$q_S$if and only if$x \in S$and the edge$S$is not part of$G$, and 3) for distinct$x$and$y$, the numbers$(p_x+1)/2$and$(p_y+1)/2$have no common prime factors except for possibly the$q_S$. In fact, this is easy: just choose the$p_x$one at a time. The conditions imposed on any one$p_x$by 2) and 3) amount to finitely many congruence conditions with prime moduli, and each prime modulus appears at most once, and none are asking$p_x\$ to be divisible by the modulus, so they are satisfiable by Dirichlet's theorem on primes in arithmetic progressions.