Question

Show that every tree with at least one edge must have at least two pendant vertices.

Short answer

Therefore, the tree with at least one edge must have at least two pendant vertices is the true statement.

Step-by-step solution

General form

Definition of tree: A tree isa connected undirected graph with no simple circuits.

Definition of rooted tree: A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

Principle of Mathematical induction: To prove that \({\bf{P}}\left( {\bf{n}} \right)\) is true for all positive integers n, where \({\bf{P}}\left( {\bf{n}} \right)\) is a propositional function, we complete two steps:

Basis step: We verify that \({\bf{P}}\left( 1 \right)\) is true.

Inductive step: We show that the conditional statement \({\bf{P}}\left( {\bf{k}} \right) \to {\bf{P}}\left( {{\bf{k + 1}}} \right)\) is true for all positive integers k.

Proof of the given statement

To prove: every tree with at least one edge must have at least two pendant vertices.

Suppose that a tree T has n vertices of degrees \({{\bf{d}}_{\bf{1}}}{\bf{,}}{{\bf{d}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{d}}_{\bf{n}}}\), respectively.

Because\({\bf{2e = }}\sum\limits_{{\bf{i = 1}}}^{\bf{n}} {{{\bf{d}}_{\bf{i}}}} \)and\({\bf{e = n - 1}}\), we have\({\bf{2}}\left( {{\bf{n - 1}}} \right){\bf{ = }}\sum\limits_{{\bf{i = 1}}}^{\bf{n}} {{{\bf{d}}_{\bf{i}}}} \).

Because each \({{\bf{d}}_{\bf{i}}} \ge {\bf{1}}\), it follows that \({\bf{2}}\left( {{\bf{n - 1}}} \right){\bf{ = n + }}\sum\limits_{{\bf{i = 1}}}^{\bf{n}} {\left( {{{\bf{d}}_{\bf{i}}}{\bf{ - 1}}} \right)} \), or that implies

\(\begin{array}{c}{\bf{2n - 2 = n + }}\sum\limits_{{\bf{i = 1}}}^{\bf{n}} {\left( {{{\bf{d}}_{\bf{i}}}{\bf{ - 1}}} \right)} \\{\bf{n - 2 = }}\sum\limits_{{\bf{i = 1}}}^{\bf{n}} {\left( {{{\bf{d}}_{\bf{i}}}{\bf{ - 1}}} \right)} \end{array}\)

Hence, at most \({\bf{n - 2}}\) of the terms of this sum can be 1 or more.

And hence at least two of them are 0. If follows that \({{\bf{d}}_{\bf{i}}}{\bf{ = 1}}\) for at least two values of

\({\bf{i}}\).

Conclusion: So, every tree with at least one edge must have at least two pendant vertices.

Hence proved.