Let $G$ be a simple graph with
$30$ vertices of degree $1$,
$6$ vertices of degree $2$,
$5$ vertices of degree $3$,
$2$ vertices of degree $4$ and
$1$ vertex of degree $5$.
Additionally, assume $G$ doesn't contain any cycles, and has no vertices of any other degree. How many connected components does $G$ have?
I know there are $44$ vertices and $n-1$ edges in a tree, which would be $43$ edges. So would the amount of connected components in $G$ be $1$?
Best Answer
Count vertices: $30+6+5+2+1=44$. Count edges: $(30+12+15+8+5)/2=35$. As you correctly state, every component must be a tree with $v_k$ vertices and $v_k-1$ edges. Since the number of edges is 9 smaller than the number of vertices, there must be 9 components.