Question

Suppose that T is an \({{\bf{S}}_{\bf{k}}}\)-tree with handle v. Show that T can be obtained from disjoint trees\({{\bf{T}}_{\bf{0}}}{\bf{,}}{{\bf{T}}_{\bf{1}}}{\bf{,}}...{\bf{,}}{{\bf{T}}_{{\bf{k - 1}}}}\) with roots\({{\bf{r}}_{\bf{0}}}{\bf{,}}{{\bf{r}}_{\bf{1}}}{\bf{,}}...{\bf{,}}{{\bf{r}}_{{\bf{k - 1}}}}\), respectively, where v is not in any of these trees, where \({{\bf{T}}_{\bf{i}}}\)is an \({{\bf{S}}_{\bf{i}}}\)-tree for \({\bf{i = 0,1,}}...{\bf{,k - }}1\), by connecting v to \({{\bf{r}}_{\bf{0}}}\) and \({{\bf{r}}_{\bf{i}}}\) to \({{\bf{r}}_{{\bf{i + 1}}}}\) for \({\bf{i = 0,1,}}...{\bf{,k - 2}}\).

Short answer

Therefore, the given statement is true. That is, \({S_k}\) can be obtained from disjoint trees \({T_0},{T_1},...,{T_{k - 1}}\) with roots \({r_0},{r_1},...,{r_{k - 1}}\), respectively, where v is not in any of these trees, where \({T_i}\) is an \({s_i}\)-tree for \(i = 0,1,...,k - 1\), by connecting v to \({r_0}\) and \({r_i}\) to \({r_{i + 1}}\) for \(i = 0,1,...,k - 2\).

Step-by-step solution

General form

Principle of \({{\bf{S}}_{\bf{k}}}\)-trees: A rooted tree T is called an \({{\bf{S}}_{\bf{k}}}{\bf{ - tree}}\) if it satisfies this recursive definition.

It is an \({S_0}\)-tree if it has one vertex. For\(k > 0\), T is an \({S_k}\)-tree if it can be built from two \({S_{k - 1}}\)-trees by making the root of one the root of the \({S_k}\)-tree and making the root of the other child of the root of the first \({S_{k - 1}}\)-tree.

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

Basis step: Verify that \(P\left( 1 \right)\) is true.

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

Proof of the statement

Given that, T is an \({S_k}\)-tree with handle v.

To prove: T can be obtained from disjoint trees \({T_0},{T_1},...,{T_{k - 1}}\) with roots \({r_0},{r_1},...,{r_{k - 1}}\), respectively, where v is not in any of these trees, where \({T_i}\) is an \({s_i}\)-tree for \(i = 0,1,...,k - 1\), by connecting v to \({r_0}\) and \({r_i}\) to \({r_{i + 1}}\) for \(i = 0,1,...,k - 2\).

Prove the above statement by induction.