3-3 HallとKőnig

$C$ は各matching辺 $e\in M$ の少なくとも一端を含みます。$M$ の異なる辺は端点を共有しないため、一つのcover頂点を二本のmatching辺の代表にはできません。各 $e\in M$ に $C$ 内の一端を対応させると単射が得られ、$|M|\le|C|$ です。最大matchingと最小coverを選べば第二式を得ます。□

coverされない辺 $xy$ があると仮定します。$x\notin X\setminus Z_X$ なので $x\in Z_X$、また $y\notin Z_Y$ です。
$xy\notin M$ なら、探索は到達済みの $x$ からこの非matching辺をたどって $y$ へ到達するので矛盾です。
$xy\in M$ なら、$x$ は未飽和rootではありません。到達したmatched $X$ 頂点は、そのmatching相手からmatching辺をたどって到達します。matching辺は一意なので相手は $y$ であり、やはり $y\in Z_Y$ です。従ってcoverされない辺はありません。□

maximum matchingにはaugmenting pathがないので、到達した全ての $Y$ 頂点は飽和されています。各 $y\in Z_Y$ のmatching相手は $Z_X$ に属します。逆に $Z_X$ のうち未飽和rootでない頂点は、ある $Z_Y$ 頂点のmatching相手として到達します。
未飽和root全体を $U\subseteq X$ とすると、matching辺は $Z_Y$ と $Z_X\setminus U$ の間に全単射を与えます。
また $X\setminus Z_X$ の頂点は全て飽和され、そのmatching相手は $Y\setminus Z_Y$ にあります。従って $M$ は

• $Z_X\setminus U$ と $Z_Y$ の間の辺、
• $X\setminus Z_X$ と $Y\setminus Z_Y$ の間の辺
  へ分かれます。ゆえに
  $$ |M|=|Z_Y|+|X\setminus Z_X|=|C|. $$
  □

maximum matching $M$ から前節の $C$ を作ると、$C$ はvertex coverで $|C|=|M|$ です。従って
$$ \tau_v(G)\le|C|=|M|=\nu(G). $$
弱双対性は逆向きの不等式を与えるので等号です。構成した $C$ はminimum vertex coverです。□

$X$ を飽和するmatchingがないと仮定すると、Kőnigの定理により大きさ $|C|<|X|$ のvertex cover $C$ があります。
$S=X\setminus C$ と置きます。$S$ から出る辺は左端でcoverされていないため、右端が全て $C\cap Y$ に入ります。従って $N(S)\subseteq C\cap Y$ です。一方
$$ |N(S)|\le|C\cap Y| =|C|-|C\cap X| <|X|-|C\cap X|=|S|. $$
これはHall条件に反します。従って $X$ を飽和するmatchingが存在します。□

任意のmatching $M$ と $S\subseteq X$ を考えます。$S$ 内で飽和できる頂点は、相異なる $N(S)$ の頂点へ対応するので高々 $|N(S)|$ 個です。従って
$$ |X|-|M|\ge |S|-|N(S)|. $$
全ての $S$ で最大を取り、さらにmaximum matchingを選ぶと
$$ \nu(G)\le |X|-\operatorname{def}(G). $$
逆向きを示します。maximum matching $M$ の未飽和 $X$ 頂点から交互探索し、到達集合を $Z_X,Z_Y$ とします。「増加路」から $N(Z_X)=Z_Y$ で、matchingは $Z_Y$ と、$Z_X$ から未飽和rootを除いた集合を全単射で結びます。未飽和root数は $|X|-|M|$ なので
$$ |Z_X|-|N(Z_X)|=|X|-|M|. $$
従って $\operatorname{def}(G)\ge |X|-\nu(G)$ です。二つの不等式を合わせて公式を得ます。□

$C$ がcoverなら、補集合内の二頂点を結ぶ辺は両端ともcover外となるため存在しません。逆に補集合がindependentなら、任意の辺の少なくとも一端が $C$ に属するので $C$ はcoverです。
補集合を取る操作が大きさ $k$ のcoverと大きさ $|V|-k$ のindependent setを対応させるため、最小と最大の間に等式が成り立ちます。□

maximum matching $M$ を取ります。$M$ で未飽和な各頂点 $v$ について接続辺を一本選び、$M$ へ加えます。未飽和二頂点を結ぶ辺は存在しません。もしあれば $M$ に追加できるからです。従って各追加辺は未飽和頂点を一つずつ新たに覆い、得るedge coverの辺数は
$$ |M|+(|V|-2|M|)=|V|-\nu(G). $$
よって $\rho(G)\le |V|-\nu(G)$ です。
逆にminimum edge cover $F$ を取り、包含についても極小にします。$(V,F)$ はcycleをもちません。cycle辺を一本除いても全cycle頂点が覆われるからです。また四頂点path $a-b-c-d$ を含めば、中央辺 $bc$ を除いても $b$ は $ab$、$c$ は $cd$ に覆われ、極小性に反します。
従って $(V,F)$ の各連結成分はstarです。各starから辺を一本選ぶとmatchingになります。成分数を $k$ とするとこのmatchingは $k$ 辺です。star forestでは
$$ |F|=|V|-k $$
なので $\nu(G)\ge k=|V|-|F|$、すなわち $|F|\ge|V|-\nu(G)$ です。両不等式から公式を得ます。□

全ての辺の右端は1,2,3のいずれかなので $C$ はcoverです。一方 $M=\{a1,b2,c3\}$ は3辺のmatchingです。弱双対性により任意のvertex coverは少なくとも3頂点必要です。従って大きさ2のcoverは存在せず、$C$ はminimumです。□

matchingは二辺を同時に選べないので $\nu(K_3)=1$ です。一頂点だけでは反対側の辺を覆えず、任意の二頂点なら全辺を覆うので $\tau_v(K_3)=2$ です。従って等号は成立しません。三角形は二部グラフでないためKőnig定理の仮定外です。□

$S=\{a,b,c\}$ では不足が $3-2=1$、全体 $X$ でも近傍が $\{1,2,3\}$ なので不足は $4-3=1$ です。他の集合の不足は1以下なので $\operatorname{def}(G)=1$。従って
$$ \nu(G)=|X|-1=3. $$
実際 $a1,b2,d3$ が大きさ3のmatchingです。□

交互の四辺を選ぶperfect matchingがあるので $\nu(C_8)=4$ です。二部グラフなので
$$ \alpha(C_8)=|V|-\nu(C_8)=8-4=4. $$
実際、一つおきの四頂点がindependent setです。□

$P_6$ は辺12,34,56からなるperfect matchingをもつので $\nu=3$、従って $\rho=6-3=3$ です。この三辺がedge coverです。
$C_5$ のmaximum matchingは2辺なので $\rho=5-2=3$。例えば辺12,34,45が全頂点を覆います。□

位置 $(1,1),(2,2),(3,3)$ にrookを置けば3個です。行が三つなので4個は不可能です。Kőnigの定理によりminimum line cover数も3で、例えば全三行を選べば実現します。□