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.
I have figured out that two computers cannot have 0 and 5 connections simultaneously but I cannot go forward from there.
On
There's no need to use the pigeonhole principle here. Suppose we could make each computer have a different number of connections. We represent each computer as a graph vertex and each connection as an edge, so the sum of degrees of vertices is $15$ (as the degree sequence must be $5,4,3,2,1,0$). But this is impossible as the sum of degrees must be even, and the statement is proved.
On
We can split this up into two cases:
Case 1: There is a computer with $0$ connections. In this case, the total number of connections for a computer is $0,1,2,3$ or $4$ (since there cannot be one with $5$ connections.). This are five options for six computers and thus, there must be two with the same number of connections.
Case 2: There is a computer with $5$ connections. In this case, the total number of connections for a computer is $1,2,3,4$ or $5$ (since there cannot be one with $0$ connections). This are five options for six computers and thus, there must be two with the same number of connections.
We can again use contradiction. You already found out that if there is a computer that is not connected to any other then other computers can have at most $4$ connections. If a computer is connected to $5$ computers then there is no computer with $0$ connection.
So you have number of direct connections for each computer between $0$ to $4$ or between $1$ to $5$. These are $5$ numbers but you have $6$ computers. So at least two of them have the same number of direct connections.