A school class has 90 students, each of whom has ten friends among(adsbygoogle = window.adsbygoogle || []).push({});

the other students. Prove that each student can invite three people at a

restaurant so that each of the four people at the table will know at

least two of the other three.

If this had to be translated to a graph it would have 90 vertices and each vertex would have 10 edges to represent friendships. I assume that when a person invites 3 other people he has an edge connecting him to the other three, so this means within such a group of 4 everybody knows at least 1. I guess the solution will have to involve the Pigeonhole principle in some form.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Graph Theory and Pigeonhole Principle

Loading...

Similar Threads for Graph Theory Pigeonhole |
---|

A About the “Axiom of Dependent Choice” |

B What is the usefulness of formal logic theory? |

I Countability of ℚ |

A Is there a decidable set theory? |

**Physics Forums | Science Articles, Homework Help, Discussion**