Question

A computer network consists of six computers. Each computer is directly connected to zero or more 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.

Short answer

The resultant answer is that at least 2 computers have the same number of direct connections.

Step-by-step solution

Given data

There are 6 computers, is the given expression.

Concept of Pigeonhole principle

If the number of pigeons exceeds the number of pigeonholes, at least one hole will hold at least two pigeons, according to the pigeon hole principle.

Simplify the expression

Consider the 6 computers to be the pigeons and the number of possible direct connections to be the pigeonholes. Every computer has either zero or more direct connections with other computers. There are two possible sets of pigeonholes, \(\{ 1\} ,\{ 2\} ,\{ 3\} ,\{ 4\} \), and \(\{ 5\} \), if there is no computer with zero direct connection, or \(\{ 0\} ,\{ 1\} ,\{ 2\} ,\{ 3\} \), and \(\{ 4\} \), if there can be a computer with zero connection. Thus, in both cases, there are at least \(\left\lceil {\frac{6}{5}} \right\rceil = 2\) computers that have the same number of direct connections.

Hence, at least 2 computers have the same number of direct connections.