引理：由于所有导出子图都存在度数 $\le k$ 的点，故整个图一定可以划分为 $k+1$ 个独立集。

构造性证明：初始时有一个空序列 $v$。依次选择度数最小的点（必然 $\le k$）加入 $v$ 的开头并删除，直到所有点都在 $v$ 中。最后，遍历 $v$，并将当前遍历到的点分配到一个独立集中。根据上述过程，加入一个点时，它的邻点中最多有 $k$ 个已经加入了某个独立集。故该点必然可以加入某个独立集。

考虑增量构造。按顺序考虑 $i=1,2,\dots,n$，尝试 $i$ 加入图中。按照上面的构造方法给 $\{1,2,\dots,i-1\}$ 划分为至多 $k+1$ 个独立集。然后询问得出 $i$ 向每个独立集 $S$ 的所有连边。由于 $S$ 是独立集，故可以询问 $\{i\} \cup S$，然后必能得到一条 $i$ 向 $S$ 中某个点 $u$ 的边。然后令 $S \gets S\backslash \{u\}$，再问，直到剩下一个独立集。这样就达成了目的。

分析询问次数：每次询问都会得到一条边，除了最后剩下一个独立集的询问。根据条件，总边数不超过 $nk$。对每个 $i$，最多出现 $k+1$ 未得到边的询问。故总询问次数不超过 $nk+n(k+1)=2nk+n$。