二分图博弈证明

情形：在二分图上某点放置一枚棋子，双方轮流移动棋子，且不能将棋子移动到已经走过的点。

（不能经过重复状态，如果是二分图）

证明：二分图中，如果初始点不必定在最大匹配上，则先手必败。

设二分图分为左右两个集合，初始点 $H$ 在左集合中。

1. 假设 $H$ 在必定在最大匹配中，那么一定不存在在右集合中且在最大匹配中的的点，有连向在左集合中除最大匹配中它所连接的一个或两个点的其他点的边。

   不然要么 $H$ 不是必选（可以用这个其他点替换掉 $H$ 成为与之等价的最大匹配，和假设必定矛盾）；

   要么当前匹配不是最大匹配，（可以用这个其他点把 $H$ 解放出来，得到更大的匹配，和假设为最大匹配矛盾）。

   由上述结论可得，若假设成立，先手选了一个匹配点后，后手必须要选最大匹配内的匹配点，即选择是确定的。

   走出第一步，相当于左集合去掉 $H$，分成选择两部分选择，其中一部分剩余左右集合相等，另一部分右集合比左集合多 1，选择第二个选法，就能保证最后选到是右集合，此时获胜。

   则 $H$ 在必定在最大匹配中时，必胜。

2. 假设 $H$ 在不必定在最大匹配中，那么先手无论选哪个点，都一定在最大匹配中。

   若设 $P$ 和 $H$ 相连，却不在最大匹配中，$P - H$ 就构成了新的匹配，原匹配就不是最大匹配了。

   后面就是先后手交换，转化为第一种情况，从一个必定在最大匹配中的点出发，所以全局的先手是必败的。

得证。

参考：二分图博弈 - Pecco