Inventory019:  A graph theory problem (proposed by Santi Spadora, 6/10/02).
Define a labeled graph G=(V(G), E(G)) where V(G)={1,2,...n} as follows: {i,j} \in E(G) iff i+j is a prime number.
(1) Prove that G is connected.
(2) Is G Hamiltonian for each n even? (It is obvious that G can't be Hamiltonian for n odd).

A few comments: Note first that G is bipartite.

Question (1) is easy to answer. It is equivalent to Tchebishev's theorem (named also Bertrand's postulate) that there always is a prime between n and 2n.
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 {p,a,x_{1},...,x_{k}} path from n to any other vertex. Thus G is connected. qed

I don't have a proof of question 2) though I believe it to be true. In the article "Some problems of combinatorial number theory related to Bertrand's postulate" by Lawrence E. Greenfield and Stephen J. Greenfield it is proven that "The integers {1, 2, ..., 2k} can be arranged into k disjoint pairs so that the sums of the
elements in each pair is prime." This is Theorem 1 of their article avaliable electronically at: http://www.emis.de/journals/JIS/green.html

Their result is another equivalent formulation of Tchebishev's theorem. Note that if it were possible to prove that for each k there always are at least two disjoint
decompositions of integers {1,2,...,2k} into k disjoint pairs of the type described in the article then 2) would follow immediately.

Example for k=2: {{1,2},{3,4}}; {{1,4},{2,3}} are two disjoint decompositions of that type and yield the Hamiltonian cycle {1,2,3,4,1}.
 

Bibliography.

Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]