グラフ理論の問題

方針：$\alpha (G)$ を「下からの評価（独立集合を作る）」と「上からの評価（頂点をクリークで覆う）」で挟み、そのあと $\alpha (G)+\tau (G)=|V|$ を使う。

下からの評価：頂点集合 $\{2,5,7\}$ を考える。$\{2,5\}$, $\{2,7\}$, $\{5,7\}$ はどれも $E$ に含まれないので、$\{2,5,7\}$ は独立集合である。よって $\alpha (G)\ge 3$。

上からの評価：辺 $\{1,2\},\{1,3\},\{2,3\}$ があるので $\{1,2,3\}$ はクリーク（三角形）、同様に辺 $\{4,5\},\{4,6\},\{5,6\}$ から $\{4,6,5\}$ もクリークである。頂点全体を
$$V=\{1,2,3\}\cup \{4,5,6\}\cup \{7\}$$
と $3$ つのクリークに分ける。独立集合はクリークから高々 $1$ 頂点しか含めない（同じクリークの $2$ 頂点は辺で結ばれている）ので、どの独立集合も大きさは $1+1+1=3$ 以下である。よって $\alpha (G)\le 3$。

以上より $\alpha (G)=3$。

$\tau (G)$ の計算：頂点集合 $S$ が独立集合であることと、その補集合 $V\setminus S$ が頂点被覆であることは同値である（辺の両端がともに $S$ に入らない $⟺$ 辺の少なくとも一方の端点が $V\setminus S$ に入る）。したがって $\alpha (G)+\tau (G)=|V|$ が成り立ち、
$$\tau (G)=7-3=4.$$
実際、$\{2,5,7\}$ の補集合 $\{1,3,4,6\}$ は $9$ 本の辺すべての端点を少なくとも $1$ つ含む頂点被覆になっている。

答え：$(\alpha (G),\tau (G))=(3,4)$

グラフの辺は、三角形 $\{1,2,3\}$、三角形 $\{4,5,6\}$、および辺 $\{3,4\},\{6,7\},\{7,1\}$ である。

【独立数】
三角形 $\{1,2,3\}$ からは高々 1 頂点、三角形 $\{4,5,6\}$ からも高々 1 頂点しか選べない。頂点 7 を加えても高々 3 頂点なので、$\alpha (G)\le 3$ である。

3 頂点の独立集合の例を探す。$\{2,5,7\}$ を調べると、辺 $\{2,5\}$、$\{2,7\}$、$\{5,7\}$ はどれも $E$ に含まれない。よって独立集合であり、$\alpha (G)=3$ である。

【最小頂点被覆】
頂点被覆の補集合は独立集合であり、逆も成り立つ。したがって $\tau (G)=|V|-\alpha (G)=7-3=4$ である（Gallai の等式）。

【検算】
$\{1,3,4,6\}$ が頂点被覆になるか調べる。
- $\{1,2\}$ は 1 を含む。
- $\{1,3\}$ は 1 を含む。
- $\{2,3\}$ は 3 を含む。
- $\{4,5\}$ は 4 を含む。
- $\{4,6\}$ は 4 を含む。
- $\{5,6\}$ は 6 を含む。
- $\{3,4\}$ は 3 を含む。
- $\{6,7\}$ は 6 を含む。
- $\{7,1\}$ は 1 を含む。

すべての辺が被覆されるので、サイズ 4 の頂点被覆が存在する。

よって $(\alpha (G),\tau (G))=(3,4)$ である。