Undirected graph G with no cycles

Question

I have an undirected graph G, which has no cycles and $n$ vertices. I will show, that G has $n-1$ edges at the most. How can I see that?

Answer 1

The statement

$\phi_n$: Let $G=(V,E)$ be a cycle-free graph with $|V|=n$, then $|E| \le n-1$

is trivial for $n=1$ (isolated vertex) and $n=2$ (at most one edge).

Suppose $\phi_n$ holds for some $n \ge 1$, and we will show it for $n+1$. So let $G=(V,E)$ be a cycle-free graph with $n+1$ many vertices. Suppose for a contradiction that all vertices of $G$ have degree $\ge 2$. In that case start at some vertex $v_0$ and pick some unused edge going out from $v_0$ to go to $v_1$. Then $v_1$ has at least one unused edge left (its degree is at least $2$ and so far we used one of its edges) and we take it to go to $v_3$ etc. If we ever meet a vertex that we used before, we have found a cycle in $G$ (from the first occurrence to the second occurrence) and this cannot happen. And we must meet a vertex again because we only have finitely many vertices. Contradiction. This shows there is some vertex $v'$ with degree $1$, with just one edge $e'$. Then $G'=(V\setminus\{v'\}, E\setminus\{e'\})$ is a cycle-free graph with $n$ vertices and so we apply the induction hypothesis $\phi_n$ to conclude

$$|E\setminus\{e'\}| \le n-1$$ which implies

$$|E| \le (n-1) + 1= n$$ as required to show $\phi_{n+1}$.