Fix \(i \in [k]\) . It suffices to show that the class \(\mathcal {H}_i\)  does not have an infinite VCL tree (VCL trees are introduced in [1]} and, intuitively, a VCL tree is a GL tree with \(k=1\)  and \(s = 1\)  everywhere). Towards contradiction, assume that \(\mathcal {H}_i\)  admits an infinite VCL tree \(\mathcal {T}= \lbrace x_u\rbrace \) . We can construct the following Graph-Littlestone tree: we use the same nodes as in \(\mathcal {T}\)  and for any node in the tree we use the coloring that colors each point with the color \(i\) . Fix an arbitrary level \(n\)  and a path \(y\) . We know that there exists a binary hypothesis \(\widetilde{h} \in \mathcal {H}_i\)  that realizes this path in the VCL tree. Due to the construction of the class \(\mathcal {H}_i\) , we have that there exists a mapping \(h \in \mathcal {H}\)  (where \(\widetilde{h} = 1\lbrace h(\cdot ) = i\rbrace )\)  that realizes the path in the constructed tree. This property holds for any path and any level. Hence, we have constructed an infinite GL tree for \(\mathcal {H}\)  which yields a contradiction.

Assume that we get \(k\)  binary classifiers \(\widehat{h}_n^{(i)}\) , one for each class \(\mathcal {H}_i\) . Finally, we set \(\widehat{h}_n(x) = \operatornamewithlimits{argmax}_i \widehat{h}_n^i(x)\)  for any \(x \in \mathcal {X}\) . The above claim concludes the proof since
\(\mathop {\bf E}\mathop {\bf Pr}_{(x,y) \sim P}[\widehat{h}_n(x) \ne y]=\mathop {\bf E}\mathop {\bf Pr}_{(x,y) \sim P}[\exists i \in [k] : \widehat{h}_n^{(i)}(x) \ne \mathbf {1}\lbrace y=i\rbrace ]\le \sum _{i \in [k]} \mathop {\bf E}[\mathrm {err}(\widehat{h}_n^{(i)})] \le 1/n\,,\) 
