# Math Help - HELP with bipartites

1. ## 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?

2. 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.

3. Thanks alot that surely helps