3-1 二部グラフとマッチング

$G$ が二部表示 $(X,Y)$ をもつとします。walkは一辺進むごとに $X$ と $Y$ の間を移ります。出発点へ戻るには偶数回移る必要があるため、すべてのcycleの長さは偶数です。
逆に $G$ がodd cycleをもたないとします。各連結成分で根 $r$ を一つ選び、$r$ からの最短pathの長さを $d(r,v)$ と書きます。距離が偶数の頂点を $X$、奇数の頂点を $Y$ に入れます。
辺 $uv$ の両端の距離が同じ偶奇だと仮定します。$r$ から $u,v$ への最短pathを取り、二つが最後に共有する頂点を $w$ とします。$w$ から $u$ への部分と $w$ から $v$ への部分は内部で交わりません。二つの長さの和は $d(r,u)+d(r,v)-2d(r,w)$ で偶数です。これに辺 $uv$ を加えると奇数長のcycleができ、仮定に反します。従って各辺は異なる偶奇の頂点を結び、$(X,Y)$ は二部表示です。非連結の場合も成分ごとに同じ操作をすればよいです。□

matchingで $S$ の各頂点に割り当てられた相手は、すべて $N(S)$ に属します。matchingの辺は端点を共有しないので、$S$ の異なる頂点は異なる相手へ割り当てられます。従って $N(S)$ には少なくとも $|S|$ 個の頂点があります。□

必要性は前の命題で示しました。十分性を $|X|$ に関する帰納法で証明します。
$|X|=0$ なら空matchingが $X$ を飽和します。$|X|=1$ なら、唯一の頂点 $x$ に対して $|N(\{x\})|\ge1$ なので隣接辺を一本選べます。
$|X|\ge2$ とし、より小さい左側頂点集合をもつ二部グラフで定理が成り立つと仮定します。二つの場合に分けます。

場合1：等号になる非自明な部分集合がある

ある空でない真部分集合 $S\subsetneq X$ が
$$ |N(S)|=|S| $$
を満たすとします。$S$ と $N(S)$ が誘導する二部グラフでは、任意の $A\subseteq S$ の近傍は元のグラフでの $N(A)$ と同じです。従ってHall条件を満たし、帰納法の仮定から $S$ を飽和するmatching $M_1$ があります。
残りの二部グラフ
$$ (X\setminus S, Y\setminus N(S)) $$
もHall条件を満たすことを示します。$T\subseteq X\setminus S$ を取ります。この残りのグラフでの近傍は
$$ N(T)\setminus N(S) $$
です。元のグラフで $S\cup T$ にHall条件を使うと
$$ |N(S\cup T)|\ge|S|+|T|. $$
一方
$$ N(S\cup T)=N(S)\cup N(T) $$
なので
$$ |N(S\cup T)| =|N(S)|+|N(T)\setminus N(S)|. $$
$|N(S)|=|S|$ を代入して
$$ |N(T)\setminus N(S)|\ge|T|. $$
従って残りにも帰納法を適用でき、$X\setminus S$ を飽和するmatching $M_2$ があります。$M_1$ の右端点は $N(S)$、$M_2$ の右端点はその外側なので、$M_1\cup M_2$ はmatchingで $X$ を飽和します。

場合2：すべての非自明な部分集合で不等号が厳しい

すべての空でない真部分集合 $S\subsetneq X$ に対して
$$ |N(S)|\ge|S|+1 $$
とします。任意の頂点 $x\in X$ を選びます。Hall条件から $x$ には隣接頂点 $y\in Y$ があります。$x,y$ とそれらに接続する辺を削除した二部グラフを考えます。
任意の $T\subseteq X\setminus\{x\}$ について、元の近傍から削除される可能性があるのは $y$ 一つだけです。$T$ は $X$ の真部分集合なので
$$ |N(T)|\ge|T|+1. $$
従って削除後も近傍の大きさは少なくとも $|T|$ です。帰納法の仮定から、削除後のグラフには $X\setminus\{x\}$ を飽和するmatching $M'$ があります。これに辺 $xy$ を加えると $X$ を飽和するmatchingになります。
二つの場合がすべてを尽くすため、十分性が証明されました。□

Hallの定理により $X$ を飽和するmatchingがあります。matchingは $|X|$ 本の辺をもち、右側で相異なる $|X|=|Y|$ 頂点を使います。従って $Y$ の全頂点も飽和し、perfect matchingです。□

まず辺数を左右から数えると
$$ r|X|=|E(G)|=r|Y|. $$
$r\ge1$ なので $|X|=|Y|$。
$S\subseteq X$ を取ります。$S$ の頂点から出る辺は各頂点 $r$ 本なので合計 $r|S|$ 本です。それらはすべて $N(S)$ の頂点へ入ります。$N(S)$ の各頂点へ入る辺はグラフ全体で $r$ 本しかないため
$$ r|S|\le r|N(S)|. $$
従って $|S|\le|N(S)|$。Hall条件が成立し、$X$ を飽和するmatchingがあります。$|X|=|Y|$ なのでperfect matchingです。□

$n$ が奇数なら $C_n$ 自身がodd cycleなので、odd cycle判定により二部グラフではありません。
$n$ が偶数なら、cycle上の頂点を順に $v_1,\ldots,v_n$ とし
$$ X=\{v_1,v_3,\ldots,v_{n-1}\},\qquad Y=\{v_2,v_4,\ldots,v_n\} $$
と分けます。連続する頂点は異なる集合に入り、最後の辺 $v_nv_1$ も偶数番と奇数番を結ぶので二部表示です。□

$S=\{a,b,c\}$ と取ると
$$ N(S)=\{1,2\},\qquad |N(S)|=2<3=|S|. $$
三人 $a,b,c$ を相異なる二つの相手1,2へ割り当てることはできません。Hall条件の必要性に反するため、全員を飽和するmatchingは存在しません。□

例えば
$$ M=\{a3,b1,c2,d4\} $$
は端点を共有せず、四人をすべて飽和します。
$$ N(\{a,b\})=\{1,2,3\},\qquad N(\{c,d\})=\{2,3,4\} $$
で、どちらも2人に対して3候補あり一つ余裕があります。特定の二人組が候補を使い切る状況ではありません。□

有限連結2-正則グラフはcycleです。実際、任意の頂点から辺をたどると次数2なので行き止まらず、有限性から頂点を再訪してcycleを得ます。連結で、cycle外へ出る辺をもつ頂点は次数が3以上になるため、成分全体がそのcycleです。
二部グラフにodd cycleはないので各cycleの長さは偶数です。偶cycleの辺を一周しながら一つおきに赤・青へ塗ると、各頂点には赤辺と青辺が一本ずつ接続します。全成分で赤辺を集めたものと青辺を集めたものが、それぞれperfect matchingです。□

必要十分条件は、すべての添字集合 $I\subseteq[n]$ に対して
$$ \left|\bigcup_{i\in I}A_i\right|\ge|I| $$
となることです。
左側頂点を添字 $1,\ldots,n$、右側頂点を和集合 $A_1\cup\cdots\cup A_n$ の要素とし、$a\in A_i$ のとき辺 $ia$ を結びます。添字集合 $I$ の近傍はちょうど $\bigcup_{i\in I}A_i$ です。相異なる代表元の選択は左側を飽和するmatchingと同じなので、主張はHallの定理そのものです。□

格子で隣接する二マスは必ず異なる色です。従って各dominoは白マス一つと黒マス一つを覆います。盤面全体を敷き詰めれば、使った白黒の個数はdomino数に等しく、白マス数と黒マス数は等しいです。
しかし同数だけでは十分でありません。座標
$$ (0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(-1,1),(1,4) $$
にある8マスだけを残した連結な盤面を考えます。座標和の偶奇で塗ると白黒は4マスずつです。しかし白マス $(0,0)$ と $(-1,1)$ は、盤面内ではどちらも黒マス $(0,1)$ だけに隣接します。この白二マスの集合 $S$ に対して
$$ |N(S)|=1<2=|S|. $$
Hall条件が破れるため敷き詰められません。十分性には全体の個数だけでなく、任意の白マス部分集合の隣接黒マス数を調べる必要があります。□