Consider a group of nine people. We know that at least one person, say Adam, knows an even number of people and does not know an even number of people. Show that either Adam and two other people all do not know each other, that some group of four people know each other, or that three people that Adam knows all do not know each other. What does this tell you about the Ramsey number r(4,3)?
I'm don't know how to begin. Can someone please walk me through this?
To start with, do you know why it's true, in a group of $9$ people, that at least one knows an even number of people? That's the "handshake lemma" of graph theory: the sum of the degrees of all the vertices is an even number (twice the number of edges); if the number of vertices is odd (in this case $9$), then at least one of them must have even degree, since the sum of an odd number of odd number is odd.
Now suppose Adam knows an even number of people (and therefore there are an even number of people he doesn't know). We want to prove that one of three statements is true:
I. Adam and two other people all do not know each other.
II. Some group of four people know each other.
III. Three people that Adam knows all do not know each other.
First, we may assume that the people Adam doesn't know all know each other; for if two of them don't know each other, then statement I holds.
Next, if there are $4$ or more people Adam doesn't know, then II holds, because those people all know each other. Therefore, we may assume that there are fewer than $4$ people that Adam doesn't know. Since the number of people he doesn't know is an even number, there are at most $2$ people he doesn't know, so there are at least $6$ people he knows.
Since $r(3,3)=6$, among the people Adam knows, there are $3$ who all know each other, or else there are $3$ who are all strangers. If there are $3$ who all know each other, we have II again. Otherwise we have III.
If II holds, we have $4$ people who know each other. If I or III holds, we have $3$ people who don't know each other. The conclusion is that $r(4,3)\le9$.
By the way, $r(4,3)$ is equal to $9$, because an easy counterexample shows that $r(4,3)\gt8$. Namely, consider $8$ people seated at a round table, and assume that each person know his neighbors on either side and the person directly opposite. Then there are no $3$ who all know each other, and there are no $4$ who all don't know each other.