Problem

Source: MOP 2005 Homework - Black Group #13

Tags: combinatorics unsolved, combinatorics



A computer network is formed by connecting $2004$ computers by cables. A set $S$ of these computers is said to be independent if no pair of computers of $S$ is connected by a cable. Suppose that the number of cables used is the minimum number possible such that the size of any independent set is at most $50$. Let $c(L)$ be the number of cables connected to computer $L$. Show that for any distinct computers $A$ and $B$, $c(A)=c(B)$ if they are connected by a cable and $|c(A)-c(B)| \le 1$ otherwise. Also, find the number of cables used in the network.