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