2022 年贵州预赛

思路

对偶图把面变顶点、面之间的公共棱变边；完美匹配指每个顶点恰好被一条所选边覆盖。这里六个面中三对相对面不相邻，得到正八面体图，可直接枚举匹配，不需要一般匹配定理。

想法从哪来：先从乙的目标倒推。若第一轮绿边就能碰到每一个面，甲第二轮怎样补红都无济于事。 一条棱恰接触两个面，因此试用三条互不重复覆盖面的棱，一次阻断六个面。把面作点、公共棱作边之后，这就是六点图里的完美匹配。 接下来不必按甲首轮三条红边逐型讨论：先数所有匹配，再数每条红边最多破坏多少匹配。若三条红边的破坏数总和仍少于全部匹配，就一定能找到完全未被甲碰到的一组。最后把这组边还原成正方体的合法绿棱。

甲最终要得到一个全红面，因此乙第一次行动若能让每个面至少出现一条绿棱，甲就必败。把正方体的六个面视为顶点、把相邻两面的公共棱视为边，得到正八面体的对偶图；问题转化为在未被甲占用的边中找一个覆盖六个顶点的完美匹配。