点 边的无向图里面选 个点,满足与其它 个点之间的连边条数为偶数,求方案数。
提示:考虑节点的度。
结论:度为偶数的点可以随便选,度为奇数的点选偶数个。
证明:
-
度为偶数的点
-
若这些点之间没有边相连,结论显然成立。
-
否则若 之间有边相连,显然若都选它们则度数都变为奇数,加起来还是偶数;若只选一个或者不选,则与情况 1 同理。
-
若更多的点之间有边相连,那么和情况 2 同理。
-
-
度为奇数的点
- 若这些点之间没有边相连,结论显然成立。
- 否则若 之间有边相连,显然若都选它们则度数都变为偶数,加起来还是偶数;若只选一个或者不选,则与情况 1 同理。
- 若更多的点之间有边相连,那么和情况 2 同理。
证毕。
赛时想了 1h。