GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 18

Question

The project of building $42$ roads connecting $16$ cities is under way, as outlined below. So far, only some of the $42$ 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?

Answer 1

Let $V_i$ be the degree of node $i$ and $e$ be the number of edges in the graph. This means digit on each city is $V_i$, and the number of roads is $e$.

The sum of all degrees will equal twice number of edges $:\displaystyle \sum_i V_i = 2e.$

Therefore, $2e=1+1+2+2+2+2+2+2+3+3+3+3+4+5+5+6=46$

$\implies e=23.$

There are $23$ complete roads among these cities.

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

So, the correct answer is $23.$

Comments

@Arjun @gatecse But sir in the picture there are two vertices of degree 4.

---

@gatecse Question needs edit. The picture of the graph showing bottom left corner node with a degree of 4, but it should be 2 according to the answer.