Problem
If a finite simple graph $G$ has exactly $|V(G)| – |E(G)|$ components, then $G$ is a forest. Prove this by induction on the number of vertices.
Solution
I reached a solution to this problem; however, I wasn't able to reach a conclusion using induction.
First, I'm going to show the solution without using induction. Then, I will show the beginning of a solution that attempts to use induction, but in which I got stuck.
Without using induction
In this solution, I'm going to use, without proof, the following theorem about finite forests, found on the textbook I'm using:
Theorem. A finite forest $F$ cosists of exactly $|V(F)| – |E(F)|$ trees.
Let $G$ be any finite simple graph with $n$ vertices and exactly $|V(G)| – |E(G)|$ components.
Then, there is a set $E \subseteq E(G)$ of edges on cycles of $G$ such that removing these edges from $G$ leaves an acyclic graph $H = G – E$. By definition, $H$ is a forest. Then, by the above Theorem, it has $|V(H)| – |E(H)|$ connected components.
Removing edges on cycles from $G$ doesn't change the number of connected components, because, for each edge $e$ that was removed from $G$, there is a path between the endpoints of $e$ that doesn't include $e$. So, $G$ and $H$ have the same number of connected components:
$$|V(G)| – |E(G)| = |V(H)| – |E(H)|$$
Since $V(H) = V(G)$ and $E(H) = E(G) – |E|$, substituting these values in the above expression yields:
$$|V(G)| – |E(G)| = |V(G)| – (|E(G)| – |E|)$$
$$|V(G)| – |E(G)| = |V(G)| – |E(G)| + |E|$$
$$|E| = 0$$
So, $G$ had no cycles to begin with. Therefore, $G$ is a forest.
Using induction
Induction hypothesis: $P(n)$ := if a finite simple graph $G$ with $n$ vertices has exactly $|V(G)| – |E(G)|$ components, then $G$ is a forest.
Base case ($n = 1$): A graph with only 1 vertex has $|V(G)| – |E(G)| = 1$ component, and it's a forest. So, $P(1)$ is true.
Inductive step ($n \geq 1$): Let $G$ be a graph with $n + 1$ vertices and $|V(G)| – |E(G)|$ components. Let $v$ be a $k$-degree vertex of $G$. Remove $v$ and all its $k$ incident edges, leaving a subgraph $H$ with $|V(G)| – 1$ vertices and $|E(G)| – k$ edges.
I got stuck at this point. Any hints on how to continue the inductive step?
Best Answer
The induction argument is essentially the same as the proof that $G$ is a tree if $V(G)-E(G)=1$. You’ve dealt with the case $|V(G)|=1$. Now suppose that $|V(G)|=n+1$.
Note first that since $G$ must have at least one component, $|V(G)|>|E(G)|$. If every vertex of $G$ has degree at least $2$, then by the handshake lemma
$$2|E(G)|=\sum_{v\in V(G)}\deg v\ge 2|V(G)|\,,$$
and $|V(G)|\le|E(G)|$; this is impossible, since $G$ has $|V(G)|-|E(G)|$ components, so $G$ has a vertex $v$ of degree at most $1$. Let $H$ be the subgraph obtained by removing $v$.
If $v$ is an isolated vertex, $E(H)=E(G)$, so $$|V(H)|-|E(H)|=|V(G)|-|E(G)|-1\,,$$ and $H$ has $|V(G)|-|E(G)|-1$ components, so by the induction hypothesis $H$ is a forest. Clearly this implies that $G$ is also a forest.
If $\deg v=1$, then $|V(H)|=|V(G)|-1$ and $|E(H)|=|E(G)|-1$, so $$|V(H)-E(H)|=|V(G)-E(G)|\,.$$ And the number of components hasn’t changed, so by the induction hypothesis $H$ is a forest, and therefore so is $G$.