Question

What is wrong with the following “proof” using mathematical induction of the statement that every tree with \({\bf{n}}\) vertices has a path of length \({\bf{n - 1}}\). Basis step: Every tree with one vertex clearly has a path of length \(0\). Inductive step: Assume that a tree with \({\bf{n}}\) vertices has a path of length \({\bf{n - 1}}\), which has \({\bf{u}}\) as its terminal vertex. Add a vertex \({\bf{v}}\) and the edge from \({\bf{u}}\)to \({\bf{v}}\). The resulting tree has \({\bf{n + 1}}\) vertices and has a path of length \({\bf{n}}\). This completes the inductive step.

Short answer

The statement said that every tree with n vertices have a path of length n-1 and this was not shown.

Step-by-step solution

Step 1:Checking the statement

This attempt indeed shows that "there exists" a tree with n vertices that has a path of length n-1. It started well because the inductive step took correctly the tree and its existence was supported by the inductive hypothesis. Nevertheless, the statement said that "every" tree with n vertices have a path of length n-1 and this was not shown.

Checking whether the proof is possible or not

Such a proof would need to start with the basis that our tree hasn+1 vertices and then show it had the required path. But since the statement is not true, such proof is not possible.