A Problem in Pigeonhole Principles.

Question

A computer network consists of six computers. Each computer is directly connected to at least one of the other computers. Show that there are at least two computers in the network that are directly connected to the same number of other computers.

I want to solve this problem with pigeonhole principle, but I can't do it.

Please give me a hint or answer.

Answer 1

Hint. What are the possible number of connections for a computer in the network? How does that compare to the number of computers?

Edit in response to comment. Since the very strong hint wasn't enough, here's a solution.

Each of the six computers might be connected to 1 or 2 or 3 or 4 or 5 of the others (since 0 is not a possibility). That's just five possible values. Since there are six computers, some value must occur twice. (That's the pigeonhole principle).

Just to test your understanding:

• Does this argument work for a network with $n$ computers, or is six special?

• Would the claim have to be true if some computers could be completely disconnected?

Answer 2

Note: the most computers any one computer connect to is 5. There just aren't any other computers to connect to.

So you have 5 possible numbers of connections, and 6 computers so... pigeon hole!