考虑对于某个整数 k>1,证明一定有方案能找到一个左部点集合 S,使得f(S) 不能被 k 整除(f(S) 的含义依然在原题题面中)。
如果权值的总和不能被 k 整除,显然可以直接选上所有左部点。
因此只需要证明权值的总和能被 k 整除的情况。
考虑找到一个最小度数的右部点 v,使其权值不能被 k 整除(存在该顶点是因为右部点权值的 \gcd 现在为 1,如果找不到显然 \gcd 都为 1)。
于是我们选择 H_v 的补集,可以发现与它有连边的右部点的权值和一定不能被 k 整除。
为什么?考虑哪些右部点与该集合没有连边,首先 v 一定是,还有 H_i\subset H_v 的所有 i(每个 i 的权值都一定可被 k 整除)。但是 v 的权值不能被 k 整除,而 H_v 的补集的答案显然为总权值和减去这些没有连边的点的权值,得证。
至于为什么都可以每个 i 的权值都一定可被 k 整除,首先 H_i=H_v,i\not=v 的情况是不存在的,因为这样他们一定会合并为一个点。考虑如果存在一个 i 使得 H_i\subset H_v 且 i 的权值不能被 k 整除,那么它的度数小于 i。由于我们选的是度数最小的点,所以这种情况不可能出现。