Forn ≥ 1, let Pn be the graph with vertex set Vn = {1,2,....,n} and two vertices are adjacent if and only if their sum is a prime number.Show thatPn is bipartite for all n ≥ 2.

Can anyone please get me started with this?

Printable View

- May 4th 2009, 07:52 AMsanorita_belleHELP with bipartitesForn ≥ 1, let Pn be the graph with vertex set Vn = {1,2,....,n} and two vertices are adjacent if and only if their sum is a prime number.
**Show that****Pn is bipartite for all n ≥ 2.**

Can anyone please get me started with this?

- May 4th 2009, 09:31 PMNonCommAlg
rule # 1 in problem solving: solve the problem for special cases whenever is possible or, in problems like yours, for small values of to get an idea how to do the general case:

let and be the set of odd and even numbers in respectively. clearly and also neither of vertices in or are adjacent because sum of any two elements of

or is an even number and thus it cannot be a prime number. Q.E.D. - May 4th 2009, 10:39 PMsanorita_belle
Thanks alot that surely helps :)