My name is Becky and I am a high school math teacher (9-12). I have the following question:
Consider a room that contains six people. Any two people are either friends of each other, or they are enemies.
A. Argue why there are three people, all who are friends,
or there are at least three people, all who are enemies
B. Rephrase the situation using graph terminology, using all of these
terms correctly: vertex, edge, graph, complement, clique, independent
set, and bipartite.
Becky, the appropriate model is a graph with two vertices joined by an edge if and only if the two people that they represent are friends. The problem is to show any such graph representing friendships among 6 people either
- contains a clique (a subgraph all of whose vertices
are completely joined together) of size 3, or
- contains the complement of a clique, i.e., an independent set (a subgraph with no edges), of size 3.
When you look at the graph pick a vertex, A; look at its adjancencies. Suppose A has 3 neighbours. If any two of these 3 neighbours are joined by an edge then we have a clique of size 3 -- these two vertices and A. If no two of those neighbours are joined by an edge then we have an independent set of size 3 -- the 3 neighbours. Thus if we could somehow guarantee that there's a vertex, like A, with 3 neighbours, we would be done. This doesn't have to be the case however, so how can we finish the proof? Suppose no such A exists, then repeat the above argument as follows. If A has at most 2 neighbours then A is independent from 3 vertices; if any 2 of these 3 are independent then we have an independent set of size 3. Otherwise these 3 vertices are all adjacent and they form a clique of size 3.
This problem is a special case of what is called Ramsey's Theorem. This is a generalization of the PieonHole Principle.
The answer is 18 people rather than 6 if we want to guarantee a clique of size 4 or an independent set of size 4. If we replace 4 by 5, no one knows the answer! It is at least 43, rather than 18, and at most 55 I believe.
I don't think you need the word bipartite in your proof.
Hope this helps,
Penny Nom