考虑在保证 $G$ 中每个点至多与两个一度点相邻的前提下不断进行删边，注意要求删边后不存在孤立点（我们希望 $S,U-S$ 内部都是完全闭合的，不依赖这条边的关系）。在先保证一度点不增加的情况下任意删边，即成为 $1,2$ 度点后邻边不可删，不妨设剩下的 $G$ 连通，连通块之间是容易合并的。则所有 $\ge 3$ 度点构成的集合 $A$ 已经是一个独立集。

若一个连通块恰为一条链则构造平凡。缩二度链后若某条链 $u-chain-v$ 上 $\ge 2$ 个点则将 $u-chain_1,chain_k-v$ 的边断开。 不妨设 $v$ 为一度点而 $u$ 为 $\ge3$ 度点则 $k\ge 1$ 时就可以删掉 $u-chain_1$ 的边，这条链同理平凡做。此时图的形态就是，忽略二度点后的 $G'$，每条边的端点要么其中恰好一个是一度点，要么中间恰好有一个点代表二度点。故度数 $\leq2$ 的点构成的集合 $B$ 也是独立集。

进一步地，当某个 $u\in A$ 连接的一度点 $<2$ 时，可以将两个连接 $\ge3$ 度点的边的一侧端点，给另一个端点添加一个叶子。这样调整出的形态，可以保证每个 $A$ 的点恰好挂两个一度点。

上面的步骤实现上只需要不断删边。将 $A$ 染色为两个大小差 $\leq 1$ 的集合 $L,R$，不妨设 $|L|\ge |R|$，对于 $u\in L$ 将挂的叶子加入 $R$ 否则加入 $L$，仍有 $|L|-|R|\leq1$。此时需要保证，$A$ 导出子图中两端点同色的边数 $\leq$ 异色的边数，因为同色确定而异色任取。问题转化为求 $L,R$，可以证明直接对满足大小限制的 $L,R$ 直接随机化是正确的：$n=2m$ 偶数时一条边 $e$ 的异色概率为 $\frac{m}{2m-1}$，$n=2m+1$ 时异色概率为 $\frac{m+1}{2m}$。直接增量或者调整也是可以的。总时间复杂度 $O(n+m)$。