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.
Best Answer
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.