Roads to 9 Cities

Probability Level 1

The project of building 20 roads connecting 9 cities is under way, as outlined above. So far, only some of the 20 roads are constructed, and the digit on each city indicates the number of constructed roads to other cities.

How many complete roads are there among these cities?

The answer is 11.

3 solutions

Worranat Pakornrat
Mar 2, 2017

Relevant wiki: Graph Theory

Let $V$ be the degree of each node and $E$ be the number of edges in the graph. As such, each digit on each city is $V$ , and the number of roads will be $E$ .

The sum of all degrees will equal twice number of edges: $\sum V = 2E$ .

Therefore, $2E = 1+1+1+2+2+3+3+4+5 = 22$ . Thus, $E = 11$ .

There are $\boxed{11}$ complete roads among these cities.

The road map with red complete tracks can be illustrated as seen below:

Thanks for showing that such a system of roads could exist.

From the point of view of a problem solver, how can we start to create this system?

Calvin Lin Staff - 4 years, 3 months ago

You're welcome.

Well, I would personally start from the 4-node, where it has least freedom as the maximum of ways is 5, so we need to cut 1 route out from one the nearby 1-nodes. From the 2 scenarios, we would logically make connection between the top left 2-node to the 5-node, etc. That should be my start.

Any suggestion is welcome. ;)

Worranat Pakornrat - 4 years, 3 months ago

Aren't there actually 2 solutions? Disconnect the top row "1" from the "2" and connect it to the center "5" (now the "5" has 6 connections, and the "2" has only 1). Connect "2" in top right to "3" below it and disconnect the "3" from the "1" below it (now the "2" has 2 connections and the bottom right "1" has none). Disconnect the bottom "3" from the "5" and connect it to the bottom right "1" (so the "5" is back to 5 connections and the bottom right "1" has 1). Was there any way to tell that there were 2 solutions without actually searching for them?

Ian Rayner - 3 years ago

Carslover14 .
Oct 17, 2017

Each road can connect 2, and only 2 cities, so sum of all digits is twice number of roads, which is 22/2=11

Rishabh Bhardwaj
Jan 25, 2018

Let suppose there are two cities (vertices) only with no road between them. Now, if I construct a road between them then it will increase the degree of both of these vertices by one (0 => 1). Summing the number of degrees of these two vertices gives me 2 while the road is one. Start increasing the number of cities and construct any number of roads you want, the degree will increase by 2 for each road you construct. So, for 'n' number of cities and 'm' as the sum of the degree of all the vertices (cities), the number of roads will be half of m.

Roads to 9 Cities

The answer is 11.

3 solutions

0 pending reports