Question

How many edges must be removed from a connected graph with $\mathrm{n}$ vertices and $\mathrm{m}$ edges to produce a spanning tree?

Answer 1

Determine to find how many edges must be removed from a connected graph:

A spanning tree of a simple graph $\mathrm{G}$ is a subgraph of $\mathrm{G}$ that is a tree and that contains all vertices of $\mathrm{G}$.

Given that connected graph $\mathrm{G}$ with $\mathrm{n}$ vertices and $\mathrm{m}$ edges.
The spanning tree contains $\mathrm{n}$ vertices because the spanning tree of $\mathrm{G}$ must have the same vertices as $\mathrm{G}$.
A tree with $\mathrm{n}$ vertices has $\mathrm{n}-1$ edges.
The number of edges that need to be removed is then the difference between the number of edges in $\mathrm{G}$ and the number of edges in the spanning tree is,
$\mathrm{m}-(\mathrm{n}-1)=\mathrm{m}-\mathrm{n}+1\mathrm{edges}$.

Hence, $\mathbf{m}\mathbf{-}\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{=}\mathbf{m}\mathbf{-}\mathbf{n}\mathbf{+}\mathbf{1}\mathbf{}\mathbf{edges}$ must be removed from a connected graph with $\mathrm{n}$ vertices and $\mathrm{m}$ edges to produce a spanning tree.