HMMT 2011 S15

On Facebook, there is a group of people that satisfies the following two properties: (i) there exists a positive integers $k$ such that any subset of $2 k-1$ people in the group contains a subset of $k$ people in the group who are all friends with each other, and (ii) every member of the group has 2011 friends or fewer. (a) [15] If $k=2$, determine, with proof, the maximum number of people the group may contain. (b) [25] If $k=776$, determine, with proof, the maximum number of people the group may contain.