Calculating connected components in an undirected graph

1.1k Views Asked by At

Suppose that we have a graph $G$ with $n$ vertices and $n-k$ edges, such that it does not include any cycles. How many connected components does it have?

1

There are 1 best solutions below

0
On BEST ANSWER

Each component is a spanning tree, and so we have $k$ such components. Note that component has $i$ has $n_{i}$ vertices and $n_{i} - 1$ edges. As a given component is connected and acyclic, it is a tree. So that's how we know it has $n_{i} - 1$ edges. And so if we know we have $n - k$ edges, then the number of edges is given by $\sum_{i} (n_{i} - 1) = n - k$ and the number of vertices is given by $\sum_{i=1} n_{i} = n$.

And so we have: $\sum_{i} (n_{i} - 1) = n - \sum_{i} 1 = n - k$, which implies $k$ components.