Any solution for this discrete math question?!?

Question

With the help of graph theory show that in any gathering of six people there are either three people who all know each other or three people none of whom knows either of the other two.

Answer 1

Don't care for graph theory, but here's my solution:

Proof by contradiction: Suppose there is no group of three people who all know each other and no group of three people who don't know each other. In what follows the property "to know" is reflexive, i.e. if X knows Y then Y knows X.

Let the six people be A, B, C, D, E and F. Now let's have a look at person A. Since there are five people besides A, person A either knows at least 3 people, or doesn't know at least 3 people.

Without loss of generality, therefore, suppose A knows each of B, C and D.

Does B know C? No, otherwise we would have A knows B knows C knows A, contradicting the hypothesis.

Does B know D? No, for the same reason.

Does C know D? No.

So it follows that B doesn't know C doesn't know D doesn't know B. This contradicts our hypothesis.

QED.

Answer 2

Graph thory is all about linkages. You need to draw things out demonstating the posibillities of relationships. Number your indivuduals 1-6 and then draw possible linkages between them. You will never find a situation where neither of the above situations is true.

I am not entirely sure how you can use Graph theory as a proof for this as I am not an expert in its use.

However this would be my best shot. Number your indivuduals 1 to 6 and place each number in a circle.

Place them into pairs 1-2, 3-4, 5,6 with a link between each of the partners ordered in a rough triange with 1-2 and 3-4 on the top and 5-6 below. Then draw linkage from 1-5, 4-6 and 2-3

At this point state that 1,3 and 6 do not know each other. (No linkage)

It is now impossible to draw a linkage from any of these to each other without a situation where 3 numbers are linked.

Answer 3

Represent the six people by six points. Now join each pair of points with a coloured line (say red) if they know each other, otherwise colour it green.

The statement in the question is equivalent to looking for either a red or a green triangle in the graph.

To prove that one triangle must exist pick one point and consider the lines that join it. There must be five as there are five other points. Now at least three of these lines must be the same colour. Let us assume there are three green ones.

Now consider the lines joining the three points at the other ends of these lines. If any of them are green then we have a green triangle. If they are all red then we have a red triangle. So the statement is proven.

Answer 4

Ask a question,then.

Answer 5

You've not asked a question.