0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – 2'5 9'2
    Apr 25, 2021 at 9:14
  • $\begingroup$ @alex.jordan yes you are right indeed, that is also another approach. Thank you for letting me know. $\endgroup$ Apr 25, 2021 at 9:19

1 Answer 1

1
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .