グラフ理論の問題

どの辺も $\{x_1,\dots ,x_5\}$ の頂点と $\{y_1,\dots ,y_5\}$ の頂点を結んでいるので、$G$ はこの 2 つを部集合とする二部グラフである。

最大マッチング. 辺 $x_2{y}_1,x_1{y}_2,x_4{y}_3,x_5{y}_5$ はどの 2 本も端点を共有しないので、大きさ $4$ のマッチングである。一方、$x_1,x_2,x_3$ の隣接頂点はすべて $\{y_1,y_2\}$ に含まれるので、$x_1,x_2,x_3$ のうちマッチングで $y$ 側と組になれるのは高々 $2$ 個である。したがって大きさ $5$ のマッチング（$x_1,\dots ,x_5$ がすべて組になるもの）は存在せず、最大マッチングの大きさは $\nu (G)=4$ である。

最小頂点被覆. $C=\{y_1,y_2,x_4,x_5\}$ を考える。$x_1,x_2,x_3$ に接続する辺の他端はすべて $y_1$ か $y_2$ であり、残りの辺 $x_4{y}_2,x_4{y}_3,x_4{y}_4,x_5{y}_4,x_5{y}_5$ は $x_4$ か $x_5$ を端点にもつ。よって $C$ は大きさ $4$ の頂点被覆である。また、マッチングの $4$ 本の辺は端点を共有しないので、どの頂点被覆もそれぞれの辺から少なくとも 1 頂点ずつ、合計 $4$ 個以上の頂点を含む。よって最小頂点被覆の大きさは $\tau (G)=4$ である（ケーニッヒの定理 $\nu (G)=\tau (G)$ とも一致する）。

最大独立集合. 一般に、$S\subseteq V$ が独立集合であることと $V\setminus S$ が頂点被覆であることは同値である（$S$ の中に両端をもつ辺がないことと、どの辺も $V\setminus S$ の頂点を端点にもつことは同じ）。したがって
$$\alpha (G)=|V|-\tau (G)=10-4=6$$
である。実際、$V\setminus C=\{x_1,x_2,x_3,y_3,y_4,y_5\}$ は、$x_1,x_2,x_3$ の隣接頂点が $y_1,y_2$ だけであり、$x$ どうし・$y$ どうしは隣接しないので、大きさ $6$ の独立集合になっている。

よって $\alpha (G)=6$ である。

$G$ は $X=\{x_1,\dots ,x_5\}$ と $Y=\{y_1,\dots ,y_5\}$ の間にだけ辺がある二部グラフである。孤立頂点はないので、ケーニッヒの定理（最大マッチングの大きさ $=$ 最小頂点被覆の大きさ）と、独立集合の補集合が頂点被覆であることから $\alpha (G)=|V|-\nu (G)$（$\nu$ は最大マッチングの大きさ）が成り立つ。

最大マッチング: $\{x_1{y}_1,x_3{y}_2,x_4{y}_3,x_5{y}_5\}$ は互いに端点を共有しない 4 本のマッチングである。
5 本は不可能: $x_1,x_2,x_3$ の隣接頂点はすべて $\{y_1,y_2\}$ に含まれ、$3$ 個の $X$ の頂点が $2$ 個の $Y$ の頂点にしか対応できない（ホールの条件の違反）ので、$X$ のすべてを覆うマッチングは存在しない。よって $\nu (G)=4$。

したがって $\alpha (G)=10-4=6$。

検算: $\{x_1,x_2,x_3,y_3,y_4,y_5\}$ を考える。$x_1,x_2,x_3$ の隣接頂点は $y_1,y_2$ のみなので $y_3,y_4,y_5$ とは辺がなく、$X$ 同士・$Y$ 同士にも辺がないので独立集合であり、大きさ 6 である。7 以上でないことは上の $\alpha =10-\nu =6$ による（頂点被覆 $\{y_1,y_2,x_4,x_5\}$ は全 10 辺を覆う大きさ 4 の被覆で、$\nu =4$ と一致する）。