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.