Graph Theory and Pigeonhole Principle

[proptrader]

A school class has 90 students, each of whom has ten friends among
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.

 

[proptrader]

I think I made a mistake in the attempt of a solution. Inviting three other people does not require that you know all three of them. The problem would ask to know only a couple for the condition to be satisfied. So I guess it comes down to proving such groups of four people can be built?
Can anyone help?

 

[Jamma]

Think about it- the question is saying that you need to pick two people who you know who also know each other. How would you do this? Suppose such a pair of people didn't exist. What would this mean looking at each of your 10 friends and all (9) of their (other) friends?

 

[Jamma]

Actually, I don't see what you mean- you said: "The problem would ask to know only a couple for the condition to be satisfied" but then "So I guess it comes down to proving such groups of four people can be built?"

Do you want your parties to be of three or four people?

 

[proptrader]

The groups should be made of 4 people as the problem says that one person invites three. In the group of four each person should know at least 2 of the others for the condition to be satisfied.

 

[proptrader]

Come on guys! Somebody has to have a clue how to approach this

 

[proptrader]

So what I've been trying to do so far is the following:
When a person invites three other students he obviously has to know two of them as the problem demands. There are 10C2 couples of such friends. The thing is for the problem to be satisfied we need the fourth person to know both of the friends that were invited. We should prove that this fourth person exists. I guess what we should do is suppose he doesn't and get a contradiction through the pigeonhole principle, but i am not sure exactly how. Any thoughts on this problem?

 

[Jamma]

Does this work?:

Take any person (A) and their 10 friends. The question of finding a party of 4 satisfying the condition that each must know 2 others is equivalent to showing that two of his friends have a common friend who can come too i.e. a common friend from the rest of the 79 (or, that you can find 3 friends of A who each knows one other of A's friends, so we'll try to rule that out). The problem is, some of A's friends may be friends with each other- but at worst each has one more friend who is already a friend with A (just picture the vertex A joined to 10 others. We can put in 5 lines between these friends before being forced to make a connection which would allow a party so it will look like 5 triangles joined at a vertex).

Right, so as a worst case scenario, we have A and his 10 friends, each who is paired off with one other of A's friends. That means each of these 10 has 8 more friends to pick. That's 80 more friends from the remaining 79. But that means that there must be two friends of A who share a common friend from the 79. Pick these two friends, along with their common friend (and the host, A, of course!) and prepare your party hats!

 

[Bacle2]

Have you considered Ramsey Numbers and Ramsey's Theorem:

http://en.wikipedia.org/wiki/Ramsey's_theorem ?

 

[Jamma]

I think my method works, but if you can come up with a proof based on Ramsey's theorem, I'd really like to hear it!

 

[Bacle2]

Jamma, I didn't mean to criticize your method; I just thought the problem may use Ramsey numbers; let me see if I can do it--after work today, since it will take me a while to refresh my Ramsey numbers.

 

[Jamma]

I wasn't saying you were Bacle. I can't immediately see how you would be able apply Ramsey theory though.

 

[proptrader]

I got a solution myself. i will try to write it up in the following days.