# Is my Graph Theory proof accurate ? Tree proof

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.

• Do you know about Euler characteristic? A tree is a connected planar graph, and $\lvert V\rvert-\lvert E\rvert+\lvert F\rvert=2$. Since it is a tree, $\lvert F\rvert=1$. So the equation becomes $\lvert E\rvert=\lvert V\rvert-1$. Apr 25, 2021 at 9:14
• @alex.jordan yes you are right indeed, that is also another approach. Thank you for letting me know. Apr 25, 2021 at 9:19

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}$$

• I added a spoiler environment because op explicitly stated he wanted to try... Apr 25, 2021 at 8:50