グラフ理論の問題

まず独立数 $\alpha (G)$（互いに隣接しない頂点を最大でいくつ選べるか）を、下からの評価と上からの評価を合わせて求める。

下からの評価（独立集合を作る）
$S=\{1,4,7\}$ を考える。頂点 $1$ に接続する辺は $\{1,2\},\{1,3\}$、頂点 $4$ に接続する辺は $\{3,4\},\{4,5\},\{4,6\}$、頂点 $7$ に接続する辺は $\{6,7\}$ だけなので、$\{1,4\},\{1,7\},\{4,7\}$ はどれも辺ではない。よって $S$ は独立集合であり、$\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$ である。

最小頂点被覆へ
頂点集合 $S$ が独立集合であることと、その補集合 $V\setminus S$ が頂点被覆であることは同値なので、
$$\alpha (G)+\tau (G)=|V|$$
が成り立つ。$|V|=7$ より
$$\tau (G)=7-3=4.$$
（確認：$V\setminus S=\{2,3,5,6\}$ は、$9$ 本の辺 $\{1,2\},\{1,3\},\{2,3\},\{3,4\},\{2,5\},\{4,5\},\{4,6\},\{5,6\},\{6,7\}$ のどれについても端点を少なくとも $1$ つ含んでおり、確かに大きさ $4$ の頂点被覆である。）

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

三角形 $\{1,2,3\}$ と三角形 $\{4,5,6\}$ は互いに頂点を共有しない。各三角形の 3 辺をすべて覆うには、その三角形の頂点が少なくとも 2 個必要である。よって $\tau (G)\ge 2+2=4$。

一方、$\{2,3,5,6\}$ は頂点被覆になる。各辺を確かめると次のとおり。
- $\{1,2\}$ は 2 を含む。
- $\{1,3\}$ は 3 を含む。
- $\{2,3\}$ は 2 と 3 を含む。
- $\{3,4\}$ は 3 を含む。
- $\{2,5\}$ は 2 と 5 を含む。
- $\{4,5\}$ は 5 を含む。
- $\{4,6\}$ は 6 を含む。
- $\{5,6\}$ は 5 と 6 を含む。
- $\{6,7\}$ は 6 を含む。

9 本すべてが覆われているので、大きさ 4 の頂点被覆が存在する。

検算として、補集合 $\{1,4,7\}$ は独立集合である（1-4、1-7、4-7 はいずれも辺でない）。最大独立集合の大きさは三角形の議論から高々 3 なので、$\tau =7-3=4$ となり一致する。

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