Proof  We prove the claim by induction over the size of the tree. Observe that a decision tree T is a full binary tree, which has 2 L ( T ) - 1 nodes, where L ( T ) is the number of leaves in the tree.

Base case. If L(T) = 1, then the original tree T consists of a single leaf node. T is the only possible pruning of itself. Thus, it is, trivially, also the smallest among the most accurate prunings of T
Inductive hypothesis. The claim holds when L ( T ) < k .

Inductive step. L(T) = k. Let N be the root of the tree and To and T 1 the left and the right subtree, respectively. Subtrees T 0 and T 1 must have strictly less than k leaves. When the pruning decision for N is taken, then - by the bottom-up recursive control strategy of REP —T n and T 1 have already been processed by the algorithm. By the inductive hypothesis, the subtrees after pruning, T ′ and T ′ , are the smallest possible among the most accurate prunings of these trees.

(i): Accuracy . The pruning decision for the node N consists of choosing whether to collapse N and the tree rooted at it into a majority leaf, or whether to maintain the whole tree.  If both alternatives make the same number of errors, then N is collapsed and the original accuracy with respect to the pruning set is retained. Otherwise, by the REP algorithm, the pruning decision is based on which of the resulting trees would make less errors with respect to the pruning set S. Hence, whichever choice is made, the resulting tree T ′ will make the smaller number of errors with respect to S .

Let us now assume that a pruning T ′′ of T makes even less errors with respect to S than T ′ . Then T ′′ must consist of the root N and two subtrees T ′′ and T ′′ , because the majority leaf cannot be more accurate than T ′ . Since T ′′ is a more accurate pruning of T than T ′ , it must be that either T ′′ is a more accurate pruning of T 0 than T ′ or T ′ is a more accurate pruning of T 1 than T 1 . By the inductive hypothesis both possibilities are false. Therefore, T ′ is the most accurate pruning of T .

(ii): Size. To see that the chosen alternative is also as small as possible, first assume that T consists of a single leaf.  Such a tree is the smallest pruning of T , and in this case the claim follows. Otherwise, T ′ consists of the root node N and the two pruned subtrees T and T i . Since this tree was not collapsed, the tree must be more accurate than the tree consisting of a single majority leaf. Now assume that there exists a pruning T* of T that is as accurate as T ′ , but smaller. Because the majority leaf is less accurate than T ′ , T ∗ must consist of the root node N and two subtrees T ∗ and T ∗ . Then, either T is a smaller pruning of T 0 than T 0 , but as accurate, or T is a smaller pruning of T 1 than T 4 , but as accurate. Both cases contradict the inductive hypothesis. Hence, T is the smallest among the most accurate prunings of T .

Thus, in any case, the claim follows for T.

口 We consider next the situation in an internal node of the tree, when the bottom-up pruning sweep reaches the node. From now on we are committed to leaf labeling by the majority of the pruning examples.