Alternative proof for the number of edges in a forest

Question

I have the following theorem:

Let G be an acyclic graph with n vertices and k connected components. Then G has n-k edges.

I have to prove the above without using induction.

My strategy is to use contrapositive. So if G does not have precisely n-k edges, then either G is not acyclic or it does not have k components.

Does that work at all? Thanks!

Answer 1

Maybe this proof avoids enough inductive reasoning to work. It does identify an invariant of a particular process, but the focus is only ever on a particular graph $G$.

• Let $G$ be an undirected acyclic graph with $k$ connected components and $e$ edges.
• Suppose you remove an edge from $G$ (assuming this is possible.) Because $G$ has no cycles, removing an edge must disconnect two components of the graph. Hence the number of edges goes down by 1, and the number of connected components goes up by one. (Also note that the resulting graph is still acyclic.)
• The quantity $k+e$ is therefore an invariant of this deletion process.
• But if you delete all of the edges in the graph $G$, you end up with the empty graph: a graph with $n$ connected components and no edges. For the empty graph, $k^\prime+e^\prime = n + 0 = n$. Hence by invariance, $k+e = n$ for the original graph $G$, as well.
• Hence $e = n-k$, as required.