# HELP with bipartites

• May 4th 2009, 07:52 AM
sanorita_belle
HELP with bipartites
For
n 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 PM
NonCommAlg
Quote:

Originally Posted by sanorita_belle

For n 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?

rule # 1 in problem solving: solve the problem for special cases whenever is possible or, in problems like yours, for small values of $n,$ to get an idea how to do the general case:

let $O$ and $E$ be the set of odd and even numbers in $V_n$ respectively. clearly $O \cup E =V_n$ and $O \cap E = \emptyset.$ also neither of vertices in $O$ or $E$ are adjacent because sum of any two elements of $O$

or $E$ is an even number $\geq 4$ and thus it cannot be a prime number. Q.E.D.
• May 4th 2009, 10:39 PM
sanorita_belle
Thanks alot that surely helps :)