KMO 2010 Problem 4

There are $n ( \ge 4 )$ people and some people shaked hands each other. Two people can shake hands at most 1 time. For arbitrary four people $A, B, C, D$ such that $(A,B), (B,C), (C,D)$ shaked hands, then one of $(A,C), (A,D), (B,D)$ shaked hand each other. Prove the following statements. (a) Prove that $n$ people can be divided into two groups, $X, Y ( \ne \emptyset )$ , such that for all $(x,y)$ where $x \in X$ and $y \in Y$ , $x$ and $y$ shaked hands or $x$ and $y$ didn't shake hands. (b) There exist two people $A , B$ such that the set of people who are not $A$ and $B$ that shaked hands with $A$ is same wiith the set of people who are not $A$ and $B$ that shaked hands with $B$ .