Jump to content

Easy Graph Theoretical question - HALP!!

bloodhound
in Linear Algebra and Group Theory

Featured Replies

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.

  • 2 weeks later...
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...

Archived

This topic is now archived and is closed to further replies.

Go to topic listing

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.