Handshake Lemma/Pigeonhole Principle

246 Views Asked by At

Given there are 27 rooms and the sum of tunnels connected to these rooms is at least 243, prove that there must exist a room that is connect to at least 10 other rooms.

I'm having trouble attacking this question, but from what I've gathered by reading it I'm thinking that both the Handshake lemma and the PHP will be needed.

I've mapped the sum of the tunnels connecting the rooms to the sum of the degrees in a graph and the individual rooms to vertices in a graph but after that I'm not sure where to proceed.

2

There are 2 best solutions below

0
On BEST ANSWER

Since $9*27=243,$ the only way that none of the vertex degrees is at least $10$ is if all of them are equal to $9$. This contradicts the handshaking lemma.

4
On

Suppose that there is no room that is connected to at least $10$ other rooms. Then every room is connected to less than $10$ rooms. So the sum of number of tunnels connected to the rooms is at most $9*27=243$, a contradiction!