# Properties of prime sum graphs

The prime sum graph $$P_n$$ on the vertex set $$V(P_n) = \{1,\dots, n\}$$ has an edge $$e = xy$$ when $$x+y$$ is prime. It is easy to show that any such $$P_n$$ is bipartite (put odd numbers in one part and evens in the other). Thus, for a Hamilton cycle to exist, $$n$$ must be even. So, set $$n=2k$$. If $$2k+1$$ and $$2k+3$$ are prime, then it is easy to see that a Hamilton cycle exists. In the case $$n = 10$$, then $$1,10,3,8,5,6,7,4,9,2,1$$ is a Hamilton cycle. Is anything else known about when these graphs are Hamiltonian? What about Eulerian?

• It's possible some sort of strong induction is possible, like in the proof that there's no subset of $\{1,\dots,2n\}$ with size greater than $n$ with no prime sum of two elements. – Carl Schildkraut May 4 '20 at 22:42
• It's much easier to see that almost NONE prime graphs are Eulerian. A connected graph is Eulerian if and only if every vertex has even degree. The degree of vertex k is the number of primes in the interval [k,n+k], where k > 1. The difference of degrees of k and k+1 equals the number of primes in {k+1,n+k+1} modulo 2. That is, a prime graph is Eulerian only if either both of them are primes, or neither of them are primes, for all k >1, which means that the two intervals [3,n-1] and [n+3,2n-1] have the same number of primes. A contradiction to the distribution of prime numbers. – Yixuan Huang May 8 '20 at 15:46