Is my Graph Theory proof accurate ? Tree proof

Question

Poof: A tree with n vertices has n-1 edges

Let us assume a tree $T = (V,E)$ such that $|V| = n,$ we know that trees are minimally connected (1-connected) graphs, and that they are maximal acyclic graphs. Hence, deleting any edge $e∈E(T)$ leads to a forest with two components (disconnecting the graph). Since Trees are maximal acyclic and adding any edge creates a cycle as a subgraph, we cannot have $n$ or more edges as that would create at least 1 cycle. We can have $n-1$ edges as that would also lead to a unique path between any two vertices $u,v∈V(T),$ which fits properties of a tree. Therefore, it must be the case that claim must be true.

Note: Is this claim possible to prove via induction? If so, then I would love to try that.

Answer 1

Yes, it can very well be proved using induction.

We assume that, by definition, the graph is connected and acyclic, and use this to prove that it has $|V|-1$ edges. We can prove this using induction on $|V|=n.$

Induction Hypothesis: Let $P(k)$ be the proposition that a connected and acyclic graph $G$, with $k$ vertices has exactly $k-1$ edges, for some $k≥0.$

Base Case: The property is clearly true for $k = 1$ as $G$ has $0$ edges. Hence $P(1)$ stands true.

Induction Step: We wish to prove that $P(k+1)$ is true, i.e. a connected and acyclic graph $G$ with $k + 1$ vertices has $k$ edges. Let $T$ be an arbitrary but particular tree with $k+1$ vertices. Let $l$ be a leaf in $T.$ Remove $l$ from $T$ to obtain $T'.$ Note that $T$ has exactly one more vertex than $T'.$ By the induction hypothesis, $T'$ has exactly $k-1$ edges, and is also connected as we removed a leaf with degree $1$. Now putting $l$ back makes the tree have one more edge as we're attaching a leaf. Hence a tree with $k+1$ vertices has exactly $k$ edges. Hence $P(k+1)$ is true.
So $P(k) \implies P(k+1),$ and $P(1)$ is true

Hence $P(n)$ is true, $\forall n \in \Re_{≥0}$