Graph Theory - How do I construct this graph?

[arunma]

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.

 

[neurocomp2003]

its a Coloring problem with a "step by step" proof. There are many similar problems. Look in a graph theory text or combinatorics text for the term colouring/coloring or the like. There's a specific chapter on this from my old text, by bondy. The only hint i should need to give you is use "color(s)"

 

[0rthodontist]

I have not done a problem like this before, but going by what Neurocomp says you can do a "step by step" proof if you start in the right place. The first thing to realize that a given node has five edges--so that the node either has at least three "friend" edges or at least three "stranger" edges. Step by step from there is not hard.