Easy Graph Theoretical question - HALP!!

[bloodhound]

First question of the first exercise sheet from my graph theory course, and I'm just stuck. Maybe I am not thinking right. Any hints are welcome

 

Questions:

Show that in any group of 6 people, either there are 3, each one of whom knows the other two, or there are 3 people none of whom knows the other two.

[RK4]

First question of the first exercise sheet from my graph theory course' date=' and I'm just stuck. Maybe I am not thinking right. Any hints are welcome

 

Questions:

Show that in any group of 6 people, either there are 3, each one of whom knows the other two, or there are 3 people none of whom knows the other two.[/quote']

 

Hi! This has to do with Ramsey Theory. I'd suggest considering another easier case before dealing with the one you're working on. The easier version is:

 

In a party with 6 people, there are either three mutual aquaintances or three mutual strangers.

 

Consider the complete graph K_6 and play around with it's complement...