**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]**