图论与组合：匹配 / MatchingsIn

因为加边不会让奇分支数量增加.

"$\Rightarrow$": 每个奇分支都至少有一条完美匹配的边与 S 相连, 且不同奇分支对应的点不同.

"$\Leftarrow$": 反证法, 假设存在 $G$ 满足条件但不含有 1-因子, 且再增加任意边都会包含一个 1-因子 (这样假设是合理的, 因为你可以不断加边直到满足, 由引理可知加边不影响 Tutte 条件, 然后可以再反推回去每个图都含有 1-因子).

设 $U=\{v\in V(G): d(v)=n(G)-1\}$

(1) G-U 是若干团的并. $o(G-U)$ 为奇团个数, 又满足 $o(G-U)\leqslant |U|$, 再结合 $U$ 的定义可知存在 1-因子.

(2) 若存在非完全的分支 $H$, 那么存在 $x,y,z\in H$, $xy,yz\in E(H),xz\notin E(H)$ 且 $y\notin U$.

因此存在 $w\notin G$, $yw\notin E(G)$.

根据假设 $G+xz$, $G+yw$ 均有完美匹配, 记作 $M_1$, $M_2$. 考虑 $M_1\Delta M_2$, 有引理 \ref{lemma::对称差} 及完美匹配性质可知对称差只包含偶环.

如果 $yw,xz$ 不在同一个偶环中, 那只要这两个偶环都取另一个匹配即可得到一个原图中的完美匹配.

如果 $yw,xz$ 在同一个偶环中, 那么 $xz, yw$ 一定存在在该偶环的两个不同的完美匹配中.

考虑加入 $yz$ 那么可以拆成一个路和一个偶环, 且最大匹配也是完美匹配.


考虑任意点集 $S$, $G-S$ 的奇分支记作 $H_1,H_2,\ldots$, 则有 $H_1,H_2,\ldots$ 在 $G$ 中互不直接相连.

考虑 $H_i$ 与 $S$ 的边数记作 $m_i$, 那么 $m_i=3n(H_i)-2e(H_i)\geqslant 1$ 且是奇数, 又整个图无割边所以 $m_i\geqslant 3$, 所以

于是 $o(G-S)\leqslant |S|$. 满足 tutte 条件.

考虑一个 2k-regular 连通图, 记作 K, 设有 n 个点. 由于是 2k 正则的, 所以存在欧拉回路记作 C.