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.