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 to get an idea how to do the general case:
let and be the set of odd and even numbers in respectively. clearly and also neither of vertices in or are adjacent because sum of any two elements of
or is an even number and thus it cannot be a prime number. Q.E.D.