本稿の目的は, 結婚定理(ホールの定理)の一般化を与えることである.
$G=(V_G,E_G)$は(有限無向)グラフ$\quad:\iff\quad V_G\ne\emptyset$は有限集合かつ$E_G\subset\{S\subset V_G: |S|=2\}$.
$V_G$は頂点の集合, $E_G$は辺の集合といい,
辺$e=\{u,v\}\in E_G$は, $u$と$v$を結ぶ辺といい, $u\dfrac{e}{\ G\ }v$, 又は, 単に$u\dfrac{e}{\quad}v$や$u\dfrac{\quad}{G}v$や$u\dfrac{}{\quad}v$で書き表す.
注意 グラフの定義から分かるように, 同じ頂点を結ぶような辺(ループ)はここでは考えていない.
$S\subset V_G$に対し, $E_G(S):=\{e\in E_G: S\cap e\ne\emptyset\},\quad \mathfrak{N}_G(S):=\left\{v\in V_G:v\dfrac{{}^\exists e}{\qquad}{}^\exists u\in S\right\}$と定める. $\mathfrak{N}_G(S)$は単に$\mathfrak{N}(S)$とも書く.
$G$をグラフ, $\nu:V_G\to\mathbb{N}$とする.
$M\subset E_G$が$\nu$マッチング$\quad:\iff\quad
|M\cap E_G(\{w\})|\le\nu(w),\quad {}^\forall w\in V_G$
$\nu$マッチング$M$は完全$\quad:\iff\quad
|M\cap E_G(\{w\})|=\nu(w),\quad {}^\forall w\in V_G$
$\nu_1:V_G\to\{1\}$とするとき, $\nu_1$(完全)マッチングを単に(完全)マッチングという.
$G$をグラフ, ${\cal F}\subset\mathfrak{P}(V_G)$とする(ここで$\mathfrak{P}(A)$は$A$の冪集合を表す).
${\cal F}$がdisjoint family (d.f.)$\quad:\iff\quad
S\cap T=\emptyset,\quad {}^\forall S,{}^\forall T\in{\cal F}$ s.t. $S\ne T$
$G$のd.f.${\cal F}$による縮約$G/{\cal F}$を
$$V_{G/{\cal F}}:=\left\{\{w\}:w\in V_G\setminus\bigcup{\cal F}\right\}\cup{\cal F},
\qquad
E_{G/{\cal F}}:=\left\{\{S,T\}\subset V_{G/{\cal F}}:S\ne T,\ S\ni{}^\exists v\dfrac{\ \ {}^\exists e\ \ }{G}{}^\exists w\in T\right\}$$
で定める.
さらに, $M\subset E_G$に対し,
$M/{\cal F}:=\left\{\{S,T\}\subset V_{G/{\cal F}}:S\ne T,\ S\ni{}^\exists v\dfrac{\ \ {}^\exists e\in M\ }{G}{}^\exists w\in T\right\}$
と定義する.
グラフ$G$は現代版結婚条件を満たす$\ :\iff\quad$ $|{\cal F}|\le|\mathfrak{N}_{G/{\cal F}}({\cal F})|,\quad {}^\forall$ d.f. ${\cal F}\subset \mathfrak{P}(V_G)$ s.t. $|S|$は奇数, ${}^\forall S\in{\cal F}$
現代版結婚条件 $\quad\Longrightarrow\quad$ 結婚条件 (二部グラフの場合には, $\iff$が成立)
注意 二部グラフの場合の$\iff$は, 次の現代版結婚定理とホールの定理の系として導かれる.
グラフ$G$が現代版結婚条件を満たす$\quad\iff\quad {}^\exists$完全マッチング
以下で現代版結婚定理の証明を与える.
完全マッチング$M$とd.f. ${\cal F}\subset\mathfrak{P}(V_G)$ ($|S|$は奇数, ${}^\forall S\in{\cal F}$)に対し, 写像$f:{\cal F}\to V_{G/{\cal F}}$を $$f(S):= \begin{cases} S & \mbox{if }S\dfrac{{}^\exists e\in M/{\cal F}}{\ G/{\cal F}\ }{}^\exists T\in{\cal F}\\ T_S & \mbox{otherwise, and }S\dfrac{{}^\exists e\in M/{\cal F}}{\ G/{\cal F}\ }T_S \end{cases}$$ を満たすものとして取れば, $M$はマッチングなので$f$は単射である. ${\rm Img}(f)\subset\mathfrak{N}_{G/{\cal F}}({\cal F})$なので, $|{\cal F}|=|{\rm Img}(f)|\le|\mathfrak{N}_{G/{\cal F}}({\cal F})|$であり, 現代版結婚条件の成立が分かる.
Tutteの定理より, $$グラフG-S:=(V_G\setminus S,E_G\cap\mathfrak{P}(V_G\setminus S))の奇数濃度の連結成分の個数\le|S|,\quad {}^\forall S\subset V_G\tag{1}$$ を示せば良い. $S\subset V_G$を固定する. また, ${\cal F}$を$G-S$において奇数濃度の連結成分全体の集合とする. 現代版結婚条件より $$|{\cal F}|\le|\mathfrak{N}_{G/{\cal F}}({\cal F})|$$ であるが, $\mathfrak{N}_{G/{\cal F}}({\cal F})\subset\{\{w\}:w\in S\}$でなければならないから $$|{\cal F}|\le|S|$$ が成り立つ. これはTutteの定理の条件(1)の成立を意味する.
グラフ$G$は二部グラフ$\quad:\iff\quad {}^\exists V^0_G\sqcup{}^\exists V^1_G=V_G$ かつ $({}^\forall e\in E_G)\left[V^0_G\ni{}^\exists u\dfrac{e}{\qquad}{}^\exists v\in V^1_G\right]$.
注意 記号「$\sqcup$」はdisjoint unionであることを表す.
表記法 二部グラフ$G$を$G=(V^0_G,V^1_G,E_G)$と書くこともある.
$G$をグラフ, $\nu:V_G\to\mathbb{N}$とする.
$G$と$\nu$は多重婚条件を満たす$\quad:\iff\quad$
$\displaystyle\sum_{w\in S}\nu(w)\le
\sum_{w\in V_G}\min\left\{\nu(w),|S\cap\mathfrak{N}_{G}(\{w\})|\right\}$,
$\quad {}^\forall
S\subset V_G$
注意 $\nu_1:V_G\to\{1\}$のときには$G$と$\nu_1$が多重婚条件を満たすとは, $G$が結婚条件を満たすことに他ならない.
二部グラフ$G$と$\nu:V_G\to\mathbb{N}$が多重婚条件を満たす$\quad\iff\quad {}^\exists$ $\nu$完全マッチング
以下, この定理の証明を行う.
$M$を$\nu$完全マッチングとする. $G$と$\nu$が多重婚条件を満たすことを示すため, 任意に$S\subset V_G$を固定する. $$\sum_{w\in S}\nu(w) =\sum_{w\in S}|M\cap E_G(\{w\})| =\sum_{w\in V_G}|M\cap E_G(S)\cap E_G(\{w\})| \le\sum_{w\in V_G}\min\left\{\nu(w),|S\cap\mathfrak{N}_{G}(\{w\})|\right\}$$ より多重婚条件の成立が分かる.
グラフ$G$と$\nu:V_G\to\mathbb{N}$と$M\subset E_G$と$w_0,w\in V_G$に対して, 互いに異なる$w_1,\cdots,w_{2n}\in V_G\setminus\{w_0,w\}$による辺の列 $$\{w_0,w_1\},\{w_1,w_2\},\cdots,\{w_{2n},w_{2n+1}\}$$ が, ($G$と$\nu$における)$w_0$と$w$を結ぶ(奇数長さの)$M$交互道であるとは, $$|E_G(\{w_{2i+1}\})\cap M|=\nu(w_{2i+1}),\ {}^\forall i< n$$ かつ $$\{w_{i},w_{i+1}\}\begin{cases} \in E_G\setminus M & i\le 2nは偶数\\ \in M & i\le 2nは奇数 \end{cases}$$ であることと定める(但し$w_{2n+1}=w$とする). さらに$w_0=w$であれば, この辺の列を$w_0$から始まる$M$交互サイクルという.
注意
$\{w_0,w\}\in E_G\setminus M$ならば, これも$M$交互道とする.
$G$が二部グラフであれば, 明らかに$M$交互道でサイクルであるようなものは存在しない.
対偶を示す. $M$を$\nu$マッチングの中で$|M|$が最大の$\nu$マッチングとする. 対偶の仮定から$M$が$\nu$完全ではない. 従って, $u\in V_G$で $$|E_G(\{u\})\cap M|<\nu(u)\tag{1}$$を満たすものが存在する. $$S:=\{w\in V_G: uとwを結ぶM交互道が存在する\}$$とおく. もしも$w\in S$で $$|E_G(\{w\})\cap M|<\nu(w)$$ を満たすものが存在すれば, $u$と$w$を結ぶ$M$交互道を"スイッチング"することで, $|M|$より辺の本数の多い$\nu$マッチングが存在して矛盾する. 従って, $$|E_G(\{w\})\cap M|=\nu(w),\ {}^\forall w\in S\tag{2}$$ が成り立つ. $$T:=\{u\}\cup\left\{w^\prime\in V_G: \{w,w^\prime\}\in M,\ {}^\exists w\in S\right\}\tag{3}$$ とおく. $M$交互道の定義から $$\{w^\prime,w\}\in E_G\setminus M かつ w^\prime\in T\ \ \Longrightarrow\ \ w\in S\tag{4}$$ である. 従って $$\begin{align} &\sum_{w\in V_G}\min\left\{\nu(w),|T\cap\mathfrak{N}_{G}(\{w\})|\right\} =\sum_{w\in V_G\setminus S}\min\left\{\nu(w),|T\cap\mathfrak{N}_{G}(\{w\})|\right\} +\sum_{w\in S}\min\left\{\nu(w),|T\cap\mathfrak{N}_{G}(\{w\})|\right\}\\ \underset{(4)より}{=} &\sum_{w\in V_G\setminus S}|M\cap E_{G}(\{w\})\cap E_G(T)| +\sum_{w\in S}\min\left\{\nu(w),|T\cap\mathfrak{N}_{G}(\{w\})|\right\} \underset{(2)より}{=} \sum_{w\in V_G\setminus S}|M\cap E_{G}(\{w\})\cap E_G(T)| +\sum_{w\in S}|M\cap E_G(\{w\})|\\ \underset{(3)より}{=} &\sum_{w\in V_G\setminus S}|M\cap E_{G}(\{w\})\cap E_G(T)| +\sum_{w\in S}|M\cap E_G(\{w\})\cap E_G(T)| =\sum_{w\in V_G}|M\cap E_{G}(\{w\})\cap E_G(T)| =\sum_{w\in T}|M\cap E_G(\{w\})|\\ \underset{(1)より}{<} &\sum_{w^\prime\in T}\nu(w^\prime) \end{align}$$ を得, 多重婚条件が$T$について成り立たないことが分かる.