1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In the second case did you mean There is not a computer with 0 connections. $\endgroup$ – PrajwalJ Oct 24 at 6:23
  • 1
    $\begingroup$ Thank you, I have corrected it. $\endgroup$ – teun Oct 24 at 6:25
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you please elaborate what "the sum of degrees must be even" mean? $\endgroup$ – PrajwalJ Oct 24 at 6:27
  • 1
    $\begingroup$ @PrajwalJ This is the handshaking lemma. $\endgroup$ – Parcly Taxel Oct 24 at 6:31

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.