The following proof is an adaptation of Proposition 23 of [1]} to the multiclass setting.

Let us first assume that \(\mathcal {H}\)  is PAC learnable in the \((k+2)\) -label multiclass setting. This implies that \(\mathrm {Ndim}_{k+2}(\mathcal {H}) \le \mathrm {Gdim}_{k+2}(\mathcal {H}) \le O(\log (k+2)) \cdot \mathrm {Ndim}_{k+2}(\mathcal {H}) < \infty \) . This implies that \(\mathcal {H}\)  is also learnable in the partial concepts setting by theorem:partial-pac-learning (by the definitions of the extended Graph and Natarajan dimensions; intuitively in the partial setting, we can use one less color). Now consider the collection of sets \(\mathbb {S} = \lbrace  \mathrm {supp}(h) : h \in \mathcal {H}\rbrace  = \lbrace  \lbrace x \in \mathcal {X}: h(x) \ne \star \rbrace  : h \in \mathcal {H}\rbrace .\)  For any sequence of \(d\)  points \(x_1,\ldots , x_d\) 
shattered by \(\mathbb {S}\) , let us take the hypothesis \(f : \mathcal {X}\rightarrow \lbrace 0,1,...,k,\star \rbrace \)  so that \(f(x_i) = \star \)  for any \(i \in [d]\) .
As an implication, this sequence \(x_1,...,x_d\)  is also shattered by
\(\lbrace  x \mapsto \mathbf {1}\lbrace h(x) = f(x)\rbrace  : h \in \mathcal {H}\rbrace \) . By the definition of the graph dimension, we get that \(\mathrm {Gdim}_{k+2}(\mathcal {H}) := \sup _{f : \mathcal {X}\rightarrow \lbrace 0,1,...,k,\star \rbrace } \mathrm {VCdim}( x \mapsto 1\lbrace h(x) = f(x)\rbrace  : h \in \mathcal {H}) \ge \mathrm {VCdim}(\mathbb {S})\) . Since \(\mathcal {H}\)  is PAC learnable in the \((k+2)\) -label multiclass setting, we get that
\(\mathrm {VCdim}(\lbrace \mathrm {supp}(h) : h \in \mathcal {H}\rbrace ) < \infty \) .
