I want to prove the following statement using mathematical induction. (This problem appears in an assignment about mathematical induction.)
For every graph $G=(V,E)$, if it doesn't contain a cycle, then $|E|\leq|V|-1$.
I know that the inequality holds when $G$ is a tree. I'm struggling to find an induction proof of this statement. I assume that we'll use induction on the number of vertices of $G$, i.e., $|V|$. Below is my attempt.
- Base case: When $|V|=1$, $|E|=0$, and the inequality holds. Hence the statement is true when $|V|=1$.
- Induction step: Let $k\geq1$ be a given integer. Suppose the statement holds for graphs with $|V|=k$.
This is where I got stuck. I don't know how to utilize the induction hypothesis and complete the induction step. Any ideas? Thanks a lot.
Let's continue the mathematical induction based on the number of vertices: Assuming that the proposition holds for a graph with $k$ vertices. Now, suppose $G$ is a graph with $k+1$ vertices. Then $G$ must have a vertex of degree 1, denoted by $v$. Otherwise, $\delta(G) \geq 2$ implies that $G$ must contain a cycle (which can be proven by considering the longest path in $G$).
Now, let $G' = G - v$. By the induction hypothesis, we have $$ |E(G')| \leq |V(G')| - 1. $$ Then, $$ |E(G)| = |E(G')| + 1 \leq (|V(G')| - 1) + 1 = |V(G)| - 1. $$ This completes the proof. \qed