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?

  • 1
    $\begingroup$ 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. $\endgroup$ May 4, 2020 at 22:42
  • 2
    $\begingroup$ 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. $\endgroup$ May 8, 2020 at 15:46


You must log in to answer this question.