I've got an exam coming up and I'm preparing some stuff w/o literature so it's quite hard to solve some exercises..

The question is:

Is it possible to make a computer network of 75 computers so that each computer is connected directly with 15 other computers? Explain.

I've thought of pigeonhole principle, but caught in a loophole.

Started off as 75 pigeons / 14 holes = maximum with 5 connections, not 15.


  • 6
    $\begingroup$ This is a graph theory question: is there a graph with 75 vertices and each vertex having degree 15? How many edges must this graph have? $\endgroup$ – Angina Seng Jan 14 '18 at 21:21

Let's try to count the number of connections between computers. If we will multiply 75 by 15 then we will count every connection twice so number of connections is 75 times 15 divided by 2 which is equal to 562,5. So we get number of connections which is not an integer so we can't get such a network. So the answer is no.


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.