Graph Theory -- How do I construct this graph? I have a question which I think I'm supposed to solve using graph theory. Here's the problem statement: "Given 6 people, suppose that the relationship between them is that they are either friends or complete strangers. Show that there must be a set of at least three people who are friends or a set of at least three people who are complete strangers." Now this isn't specifically a graph theory course, but I'm guessing that I have to construct a graph with six nodes. A few questions: how many edges should the graph have? Is it necessary to use a directed graph? And where should I place the edges with respect to the nodes? I'm fairly certain that if I can construct the right graph, the problem will become almost trivial. Anyway, I'd really appreciate some help with this if anybody is able. I've been thinking about this problem for some time now, and it's starting to drive me crazy. Thanks in advance.