グラフ理論の問題

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

下からの評価 頂点集合 $\{2,5,7\}$ を考える。$2$ に接続する辺は $\{1,2\},\{2,3\}$、$5$ に接続する辺は $\{4,5\},\{5,6\}$、$7$ に接続する辺は $\{1,7\},\{6,7\}$ であり、$\{2,5\},\{2,7\},\{5,7\}$ はどれも辺ではない。よって $\{2,5,7\}$ は独立集合で、$\alpha (G)\ge 3$。

上からの評価 辺 $\{1,2\},\{1,3\},\{2,3\}$ があるので $\{1,2,3\}$ はクリーク（三角形）であり、辺 $\{4,5\},\{4,6\},\{5,6\}$ があるので $\{4,5,6\}$ もクリークである。$V$ は
$$V=\{1,2,3\}\cup \{4,5,6\}\cup \{7\}$$
と $3$ つのクリークに分けられる。独立集合は $1$ つのクリークから高々 $1$ 個の頂点しか含めない（クリーク内の $2$ 頂点は必ず隣接する）ので、独立集合の大きさは高々 $1+1+1=3$。よって $\alpha (G)\le 3$。

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

頂点被覆へ 独立集合の補集合は頂点被覆であり、逆も成り立つので $\alpha (G)+\tau (G)=|V|$。$|V|=7$ より
$$\tau (G)=7-3=4.$$
実際、$\{2,5,7\}$ の補集合 $\{1,3,4,6\}$ は、$9$ 本の辺 $\{1,2\},\{1,3\},\{2,3\},\{3,4\},\{4,5\},\{4,6\},\{5,6\},\{1,7\},\{6,7\}$ のどれについても少なくとも一方の端点を含んでいる。

したがって $(\alpha (G),\tau (G))=(3,4)$。

グラフの隣接関係は 1:{2,3,7}, 2:{1,3}, 3:{1,2,4}, 4:{3,5,6}, 5:{4,6}, 6:{4,5,7}, 7:{1,6} である。

【独立数】$\{1,2,3\}$ と $\{4,5,6\}$ はそれぞれ三角形（完全グラフ $K_3$）なので、独立集合はそれぞれから高々 1 頂点しか選べない。残りの頂点は 7 だけだから、$\alpha (G)\le 1+1+1=3$ である。
実際に $\{2,4,7\}$ を調べると、辺 $\{2,4\},\{2,7\},\{4,7\}$ はいずれも $E$ に含まれないので独立集合である。よって $\alpha (G)=3$。

【最小頂点被覆】頂点集合 $S$ が独立集合であることと、補集合 $V\setminus S$ が頂点被覆であることは同値である。したがって $\tau (G)=|V|-\alpha (G)=7-3=4$（ガライの恒等式）。

【検算】$\{1,3,4,6\}$ が頂点被覆か確かめる。
12(1), 13(1), 23(3), 34(3), 45(4), 46(4), 56(6), 17(1), 67(6) と、全 9 辺が被覆される。大きさ 4 の被覆が存在する。
$\tau \ge 4$ も確認できる。各三角形を被覆するには 2 頂点ずつ必要で、$\{1,2,3\}$ と $\{4,5,6\}$ は頂点を共有しないから、合計で少なくとも 4 頂点が必要である。

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