GATE CS 2017 Set 1 Q.20 (CS Q.20): Graph Theory

Let $T$ be a tree with 10 vertices. The sum of the degrees of all the vertices in $T$ is ______.

Your answer

Official answer and solution

Solution

Apply the Handshaking Lemma to the number of edges in a tree with 10 vertices.

A tree with $n$ vertices is a connected acyclic graph and contains exactly $n - 1$ edges. For $n = 10$ , the number of edges is:

|E| = 10 - 1 = 9

According to the Handshaking Lemma, the sum of the degrees of all vertices in any undirected graph is equal to twice the number of edges:

\sum_{v \in V} \text{deg}(v) = 2 |E| = 2 \times 9 = 18

Final answer

18.0

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.