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.

  • $\begingroup$ 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. $\endgroup$ – 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).

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?

  • $\begingroup$ I am thinking about. . . But i can't solve the problem . . . 😂 $\endgroup$ – kiseoking Oct 29 '16 at 13:11

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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.