ABC262E Red and Blue Graph 做题记录

$n$ 点 $m$ 边的无向图里面选 $k$ 个点，满足与其它 $n-k$ 个点之间的连边条数为偶数，求方案数。

提示：考虑节点的度。
 

结论：度为偶数的点可以随便选，度为奇数的点选偶数个。

证明：

• 度为偶数的点

  1. 若这些点之间没有边相连，结论显然成立。

  2. 否则若 $u,v$ 之间有边相连，显然若都选它们则度数都变为奇数，加起来还是偶数；若只选一个或者不选，则与情况 1 同理。

  3. 若更多的点之间有边相连，那么和情况 2 同理。

• 度为奇数的点

  1. 若这些点之间没有边相连，结论显然成立。
  2. 否则若 $u,v$ 之间有边相连，显然若都选它们则度数都变为偶数，加起来还是偶数；若只选一个或者不选，则与情况 1 同理。
  3. 若更多的点之间有边相连，那么和情况 2 同理。

证毕。

赛时想了 1h。