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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s