219 views

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

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

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.