Let a graph has 6 components and 30 edges .what is the maximum possible number of vertices of G ? The problem seems to me interesting. Here each component may not have the same edges .Then how to approach the problem. I only know sum of the degree if all vertices = twice the number of edges. Any help would be appreciated. Thanks in advance.
Hint: A tree is a connected graph with no cycles. The following facts are useful:
- A tree with $n$ vertices must have $(n-1)$ edges
- A connected graph is a tree if and only if removing any edge will disconnect the graph
If we are to have as many vertices as possible, then each of the $6$ components of the graph must be a tree.
Suppose that the components have $E_1,E_2,\dots,E_6$ many edges respectively. The total number of edges is 30, which is to say that $$ E_1 + E_2 + \cdots + E_6 = 30 $$ Since each component is a tree, the number of vertices in the $i$th component must be $E_i + 1$. So, the total number of vertices is $$ (E_1 + 1) + (E_2 + 1) + \cdots + (E_6 + 1) $$ which is necessarily $36$ (why?).