## Solution to Puzzle #64: Unique Country

I think I went a little bit overboard with the puzzle I posted last week…did not get any correct answer. Was hoping that there must be some Computer Scientists who will send me the answer!

Anyway the answer is that there cannot be 100 roads in a country where every city has exactly 3 roads connecting the city. The solution lies in two concepts – simple graph theory, and divisibility by 3.

Think of this country as a graph, where each road is an edge, and each city is a vertex. We therefore need to build a graph with 100 edges where the degree of each vertex is exactly 3…the keyword being “exactly”. If we were to add the degrees of each of the vertex (or city), then the sum should be 200, as each edge (or road) contributes to 2 degrees (one each for the two cities it connects). Since 200 is not divisible by three, such a graph is not possible.

Hope you enjoyed the puzzle!

This entry was posted in Solution and tagged , . Bookmark the permalink.