Dark Mode

219 views

3 votes

For which of the following does there exist a graph satisfying the specified conditions?

- A tree with six vertices and six edges.
- A tree with three or more vertices, two vertices of degree one, and all the other vertices with degree three or more.
- A disconnected graph with $10$ vertices and $8$ edges.
- A disconnected graph with $12$ vertices and $11$ edges and no cycle.

3 votes

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.