GO Classes Scholarship 2023 | Test | Question: 10

Answer 1

A. No such tree exists. A tree with six vertices must have five edges.
B. Assume such a tree exists. Let a number of vertices be $n$.

Then Total degree $=2(n-1)$

Total degree $\geq(1+1)+3(n-2)$

So, $2(n-1)\geq3 n-4$

Which is a contradiction. Hence, no such tree exists.

Method 2:
Every tree with maximum degree $\Delta>1$ has at least $\Delta$ leaves.
Let the maximum degree of a vertex in a tree be $\Delta$. Then there are at least $\Delta$ leaves in the tree i.e. at least $\Delta$ vertices of degree $1.$

For option B, No such tree exists. Such a tree must have at least one vertex of degree three or more and hence at least three vertices of degree one.
C. A graph with two connected components, each a tree, each with five vertices, will have this property.
D. No such graph exists. Disconnected Acyclic graph has less than $n-1$ edges for $n$ vertices.