Infinite graph with Legendre symbol . Consider a (kind of) infinite oriented graph as follows :
1.The vertexes represent the prime numbers $p>2$ .
2.We draw an oriented edge from $p$ to $q$ if $\left(\frac{p}{q} \right )=1$ (this is the Legendre symbol ) . Note that we are allowed to have both orientations between two primes . 

Prove that this graph is connected in the sense that if $p$ and $q$ are two primes then there are (at least) two oriented paths between them : one from $p$ to $q$ and one from $q$ to $p$ .

If you want a challenge : Find other interesting properties of this graph . Or maybe prove that the corresponding graph with the Jacobi symbol (this time between all numbers $>1$ ) is connected .
I have no idea how to prove this so I ask here for help . 
Thanks to anyone who tries to solve these awesome problems .
 A: Fix $p$ and $q$, distinct odd primes.  Let's break it down to a couple of cases:
Case 1: $p$ and $q$ are both $3 \pmod{4}$.
Then $\left(\frac{p}{q} \right) = - \left(\frac{q}{p} \right)$ by quadratic reciprocity.  Thus, we may assume without loss of generality that $ \left(\frac{p}{q} \right) = -1$.  Since Dirichlet's Theorem tells us that there is a prime $r$ satisfying $r \equiv 1 \pmod{4pq}$ (in fact it tells us that there are infinitely of them.  Chinese remainder theorem tells us that $r \equiv 1 \pmod{4}$, $r \equiv 1 \pmod{p}$, and $r \equiv 1 \pmod{q}$,  since $p,q$, and $r$ are coprime.  We thus have that $$\left(\frac{p}{r} \right)   = \left(\frac{r}{p} \right) = \left(\frac{1}{p} \right) = 1.$$ where the first is by Quadratic Reciprocity (recall $r \equiv 1\pmod{4}$), and the second is due to the fact that $r \equiv 1 \pmod{p}$.  Thus there is an oriented edge from $p$ to $r$.  Similarly, we have $$ \left(\frac{r}{q} \right) = \left(\frac{1}{q} \right) = 1.$$
Thus there is an edge from $r$ to $q$.  There is thus a path from $p$ to $r$ to $q$.  Recall that $\left(\frac{q}{p} \right) = 1$ by Quadratic reciprocity so this completes the first case.
Case 2: Either $p$ or $q$ is $1 \pmod{4}$.
Then $\left(\frac{p}{q} \right) = \left(\frac{q}{p} \right)$.  If both Legendre symbols are $1$, then we are done.  Thus, we may assume that both are $-1$.  Similarly, find a prime $r \equiv 1 \pmod{4pq}$.  Then by the above logic, we have $$\left(\frac{p}{r} \right) = \left(\frac{r}{p} \right) = \left(\frac{1}{p} \right) = 1.$$
Similarly, $$\left(\frac{r}{q} \right) = \left(\frac{1}{q} \right)  = 1.$$
Thus, we have a path from $p$ to $r$ to $q$.  Since $r \equiv 1\pmod{4}$, these edges can be reversed by Quadratic Reciprocity, competing the proof.
