Question

How many edges must be removed to produce the spanning forest of a graph with n vertices, m edges, and c connected components?

Short answer

The number of edges is\({\bf{m - n + c}}\).

Step-by-step solution

Compare with the definition.

A spanning tree of a simple graph G is a subgraph of G that is a tree and that contains all vertices of G.

A tree is an undirected graph that is connected and does not contain any single circuit. And a tree with n vertices has\({\bf{n - 1}}\)edges.

Find the edges.

Let the number of vertices in the components of a graph G be\({\bf{(}}{{\bf{n}}_{\bf{1}}}{\bf{,}}{{\bf{n}}_{\bf{2}}}{\bf{,}}....{{\bf{n}}_{\bf{c}}}{\bf{)}}\)\(\sum\limits_{{\bf{i = 1}}}^{\bf{c}} {{{\bf{n}}_{\bf{i}}}} {\bf{ = n}}\). That is, the total no. of vertices in G. Hence the ith-spanning tree of the spanning forest of G must have\({\bf{(}}{{\bf{n}}_{\bf{i}}}{\bf{ - 1)}}\) edges. As if contains all the vertices of the corresponding connected component of G. Thus, the number of edges removed as\({\bf{m - }}\sum\limits_{{\bf{i = 1}}}^{\bf{c}} {{\bf{(}}{{\bf{n}}_{\bf{i}}}{\bf{ - 1)}}} {\bf{ = m - n + c}}\).

Therefore, the number of edges is \({\bf{m - n + c}}\).