# 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 \$\displaystyle n,\$ to get an idea how to do the general case:

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

or \$\displaystyle E\$ is an even number \$\displaystyle \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 :)