Hamiltonicity in Prime Sum Graphs

For any positive integer n, we define the prime sum graph $$G_n=(V,E)$$ of order n with the vertex set $$V=\{1,2,\cdots , n\}$$ and $$E=\{ij: i+j \text{ is } \text{ prime }\}$$ . Filz in 1982 posed a conjecture that $$G_{2n}$$ is Hamiltonian for any $$n\ge 2$$ , i.e., the set of integers $$\{1,2,\cdots , 2n\}$$ can be represented as a cyclic rearrangement so that the sum of any two adjacent integers is a prime number. With a fundamental result in graph theory and a recent breakthrough on the twin prime conjecture, we prove that Filz’s conjecture is true for infinitely many cases.