【Analysis】Similar to Example 9 in [1], the proof method for Turán's theorem uses a random permutation of vertices. To ensure no complete graph $K_{k+1}$ appears, it is sufficient to require that the degree of each vertex in graph $H$ does not exceed $k-1$. For a random permutation of vertices $v_{1}, v_{2}, \cdots, v_{n}$, using a greedy algorithm, select $v_{i}$ if and only if, in the permutation of $v_{i}$ and its adjacent vertices, $v_{i}$ is among the first $k$ positions. This ensures that the degrees of the selected vertices do not exceed $k$, and thus, the final graph contains no $K_{k+1}$. Next, we prove that the expected number of selected vertices is at least $\frac{k n^{2}}{2 e+n}$.

Let $X_{i}$ be the random variable indicating whether the $i$-th vertex is selected in a random permutation, taking the value 1 if selected and 0 otherwise.

Notice that, in the permutation of $v_{i}$ and its adjacent vertices, $v_{i}$ will be selected if it is among the first $k$ positions. Thus,
$$\begin{array}{l} \mathrm{E}\left(X_{i}\right)=1 \cdot P\left(X_{i}=1\right)+0 \cdot P\left(X_{i}=0\right) \\ =\frac{k}{d_{i}+1} . \end{array}$$

Let the random variable $X$ represent the number of vertices that can be selected according to the required algorithm in a random permutation, then
$$\begin{array}{l} X=X_{1}+X_{2}+\cdots+X_{n} \\ \Rightarrow \mathrm{E}(X)=\sum_{i=1}^{n} \mathrm{E}\left(X_{i}\right)=\sum_{i=1}^{n} \frac{k}{d_{i}+1} . \end{array}$$

By the Cauchy-Schwarz inequality, we have
$$\mathrm{E}(X)=\frac{k n^{2}}{\sum_{i=1}^{n}\left(d_{i}+1\right)}=\frac{k n^{2}}{2 e+n} \text {. }$$

Therefore, there must exist a permutation such that the number of selected vertices is at least $\frac{k n^{2}}{2 e+n}$.
This completes the proof.