A051252 - Prime Circles - Summary and Update

Santi Spadaro santi_spadaro at virgilio.it
Tue Jun 25 22:48:46 CEST 2002

>Consider the graph G(m) which has vertex set {1,2,...,m} and
>where (i,j) is an edge if and only if i+j is prime. For example, the
>graph G(8) has
>  vertices: 1, 2, 3, 4, 5, 6, 7, 8
>  edges: (1,2) (1,4) (1,6) (2,3) (2,5) (3,4) (3,8) (4,7) (5,6) (5,8) (6,7)
>The question raised by Santi is
>	"Is G(2m) hamiltonian for all values of m?"
Another possible generalization is to change the vertex set. Call G' the
graph whose definition for the edge set is the same of G, but with vertex
set {1,4,9,16,...,n^2}.

Here is the number of Hamilton Cycles in G'(2n): 1<=n<=7


Note that we don't even know if G' is connected, while I have proved that G
is connected for each n:

Proof: (induction on n): for n=2 the statement is true since
V(G)={1,2} and 1+2=3 is prime. Suppose now it is true for n-1, by
Tchebishev's theorem there always is a prime p such that n<p<2n, thus
p=n+a where a <n so a is in {1,2,...,n-1}. By the induction step there
always is a path from a to any other vertex in {1,2,...,n-1}, call it
{a, x_{1},...,x_{k}}. Then {n,a,x_{1},...,x_{k}} path from n to any
other vertex. Thus G is connected. qed

Computational checking suggests that also G' is connected, but I don't know
how to prove it.


More information about the SeqFan mailing list