A tree with n vertices has (n-1) edges: Proof

A tree with n vertices has (n-1) edges. For example, a tree with 5 vertices should have 5-1=4 edges. In this post, we prove that a tree contains (n-1) edges if it has n vertices.

A tree of n vertices has n-1 edges

Theorem: Show that a tree with n vertices has (n-1) edges.

Proof:

Let P(n) denote the statement P(n):= A tree of n vertices has (n-1) edges.

Base Case:

To show P(1) is true.

We know a tree of only one vertex has no edge. Thus, P(1) is true.

Induction Hypothesis:

Assume that P(k) is true for k = 1, 2, 3, …, n-1. That is, a tree of less than n vertices has the above property. Assuming this, we will show that P(n) is true in the next step.

Induction Step:

To show, P(n) is true, let us consider a tree T of n vertices.

Let e be the edge connecting two vertices u and v. So by definition of a tree, e is the only path between u and v.

Now, delete the edge e.

Thus T becomes disconnected. Hence, T-e has two connected components, say T₁ and T₂. As T has no circuit, we conclude that both T₁ and T₂ have no circuits. Now, since T₁ and T₂ are connected graphs with no circuits, it follows that both are trees.

Suppose T₁ has $r$ vertices and T₂ has $(n-r)$ vertices with 1 ≤ r ≤ n. As both T₁ and T₂ have less than $n$ vertices, applying induction hypothesis to T₁, T₂ we obtain that T₁ has $(r-1)$ edges and T₁ has $(n-r)-1$ edges.

Therefore, total number of edges of T = Number of edges of T1 + Number of edges of T2 + 1 [we have added 1 because of the deleted edge u]. = $r-1+(n-r)-1+1$ = $n-1$.

Thus, T has (n-1) edges.

Conclusion:

So by mathematical induction, we conclude that $P(n)$ is true for $n=1,2 ,\cdots$. Hence a tree with $n$ vertices has $(n-1)$ edges, for any integers $n \geq 1$. This completes our proof.

Also Read: Simple Graph has Two Vertices of Same Degree: proof

Homepage of Discrete Mathematics

FAQs