graph theory problem on computer communication

73 Views Asked by At

Can someone please help me to do this problem:
There are 1958 computers which can communicate among themselves in six languages with the condition that any two computers can communication with only one language out of 6 languages.Prove that there are at least three computers whose mutual language of communication is the same

1

There are 1 best solutions below

3
On BEST ANSWER

Fix one of the computers. It communicates to $1957$ other computers in six possible languages, so it will communicate to $\lceil \frac{1957}{6} \rceil = 327$ computers in the same language. If any pair of those $327$ computers communicate in that language, we are done. Otherwise, we have reduced the problem from six to five languages.