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 $\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 PMsanorita_belle
Thanks alot that surely helps :)