Number of connected components in a graph with n vertices and n-k edges

Question

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.

Answer 1

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?

Answer 2

So you have a number of components, but don't know how many. Each component is connected and acyclic, which means each component is a tree. And so by tree properties, each component has $n_{i}$ nodes and $n_{i} - 1$ edges. So if we have $n$ nodes in the graph, we have:

$\sum_{i} n_{i} = n$ and $\sum_{i} (n_{i} - 1) = n - k$. It follows that $$\sum_{i} (n_{i} - 1) = \sum_{i} n_{i} - \sum_{i} 1 = n - \sum_{i} 1 = n - k$$

And so $\sum_{i} 1 = k$, which implies $k$ components.