Graph Theory - An Introduction

An introduction to basic graph theory through the problem of six people at a party. Robin Wilson, Gresham Professor of Geometry, shows how a good diagram can easily prove that at any party of six people, at least three will either be friends or enemies. In the process, Professor Wilson demonstrates the basics of graph theory.

This is the 18th part of 'A Millennium of Mathematical Puzzles'.
The full lecture is available (in 24 parts) here on YouTube, or it can be downloaded (like all of our lectures) in its complete form from the Gresham College website, in video, audio or text formats:
http://www.gresham.ac.uk

Gresham College has been giving free public lectures since 1597. This tradition continues today with all of our five or so public lectures a week being made available for free download from our website.

Category:

Education

Tags:

• Math
• Maths
• Mathematics
• Wilson
• Geometry
• Fraction
• Problem
• Puzzle
• Lecture

[tomatotoesnsocks]

@pkiverson yes. he didnt set the stage well, but the answer is intuitive anyway

[pkiverson]

@cardiganmimi If there were 5 or fewer people, you can't guarantee there will be 3 mutual acquaintances or 3 mutual strangers. If you think of the 5 people sitting in a circle, assume they are all strangers with the two people to the side of them, but acquaintances to the two people across from them. In this scenario, you don't have 3 mutual strangers or 3 mutual acquaintances. The more you know...

[cardiganmimi]

why did you need 6 people?

[irda2008]

What the fuck is he saying. There are n-possible choices regarding the mutual relationships between these six persons.