# A Problem in Pigeonhole Principles.

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.

• If every computer is hooked to a different number of connections and none are hooked up to 0 then there is one computer with 6 or more connections. But there are only 5 computers for it to be connected to. – fleablood Oct 29 '16 at 16:19

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).

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