A tree with prime vertices

Question

Let us construct a simple (undirected) graph $T$ as follows:

$\quad$ Let the set of all primes be the vertex set of $T$. For each prime $p$, take the least prime $q>p$ such that $2(p+1)-q$ is prime (such a prime q should exist in view of Goldbach's conjecture), and then set an edge connecting $p$ and $q$.

Clearly the graph $T$ contains no circle. If it is connected then it is a tree.

QUESTION. Is the above graph $T$ a tree?

In Feb. 2013, I constructed the graph $T$ and conjectured that $T$ is indeed a tree. For example, the path connecting $2$ and $191$ is \begin{align*}2&\to 3\to 5\to 7\to 11\to 13\to 17\to 19\to 23\to 29\to 31\to 41, \\ &\to43\to 47\to 53\to 61\to 71\to 73\to 89\to 97\to 107\to 109 \\&\to 113\to 127\to 149\to 151\to 167\to 173\to 181\to 191. \end{align*}

Any ideas towards the solution of the question? Your comments are welcome!

Answer 1

Not an answer, just a drawing of the tree including the OP's $2 \rightarrow 191$ path:

---

         

---

Answer 2

This does not give a complete answer. This provides a strategy for conditional approach.

Given that the nature of the problem is asking for $q$ and $2(p+1)-q$ being simultaneously primes, I think that the question can be approached conditionally (similar to zz7948).

A slight modification is shifting the focus to finding $p<q$ such that $p$ and $2p+2-q$ are simultaneously prime, for given prime $q$. As suggested in zz7948's comment, we extend the edges to include all pairs $(p,q)$ with both $p$ and $2p+2-q$ are primes.

Let us assume the following version of prime $k$-tuple conjecture.

Conjecture 1

There is an absolute constant $C>0$ and a prime $q_0$ such that the number $N(q)$ of primes $p<q$ such that $p$ and $2p+2-q$ are simultaneously prime satisfies $$ N(q)\geq C\frac q{\log^2 q}\geq 1, \ \ \mathrm{ if } \ q\geq q_0. $$

If Conjecture 1 is true, then any prime $q>q_0$ is connected to some smaller prime.

If we can show (computation) that all primes $q\leq q_0$ are connected, then all primes will be connected.

Once we obtain that all primes are connected, we now start to remove the edges to include only the smallest $q$ with $q>p$ and $2p+2-q$ are both primes.

Then, the issue is, whether or not Prim's algorithm of finding spanning tree of a connected graph gives the desired graph.