Suppose that we have a graph G with n vertices and n-k edges, such that it does not include any cycles. How many components does it have?
I am coming up with k components but am having a hard time proving it. Please help.
[Math] Number of connected components in a graph with n vertices and n-k edges
graph theory
Best Answer
If there are no cycles, $G$ is a collection of trees. Do you know a relationship between the vertices and edges in a single tree?