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$?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.