グラフ理論の問題

辺を列挙する。 相異なる 2 頂点の和は $1+2=3$ 以上 $14+15=29$ 以下なので、和になりうる平方数は $4,9,16,25$ である。

• 和が $4$: $\{1,3\}$
• 和が $9$: $\{1,8\},\{2,7\},\{3,6\},\{4,5\}$
• 和が $16$: $\{1,15\},\{2,14\},\{3,13\},\{4,12\},\{5,11\},\{6,10\},\{7,9\}$
• 和が $25$: $\{10,15\},\{11,14\},\{12,13\}$

よって辺は全部で $15$ 本である。つなぎ方をたどると、$G$ は
- 閉路 $1-15-10-6-3-1$（長さ $5$）
- 頂点 $1$ にだけつながる頂点 $8$（次数 $1$）
- 頂点 $3$ から伸びる道 $3-13-12-4-5-11-14-2-7-9$

からなる。

上界. 独立集合 $S$ に対し、その補集合 $V\setminus S$ は頂点被覆（どの辺も少なくとも一方の端点を含む）である。いま
$$\{8,1\},\{15,10\},\{6,3\},\{13,12\},\{4,5\},\{11,14\},\{2,7\}$$
はどれも $G$ の辺で、互いに端点を共有しない $7$ 本の辺（マッチング）である。頂点被覆はこれら $7$ 本の辺それぞれから少なくとも 1 つの端点を含み、それらは相異なるので、頂点被覆の大きさは $7$ 以上である。したがって $|S|=15-|V\setminus S|\le 15-7=8$。

構成. $S=\{8,15,6,13,4,11,2,9\}$ を考える。上の辺の一覧のどの辺も、両端がともに $S$ に入ってはいない（たとえば $S$ のどの 2 数の和も $4,9,16,25$ にならない）ので、$S$ は大きさ $8$ の独立集合である。

（見つけ方：次数 $1$ の頂点 $8$ は最大独立集合に入れてよく、そのとき $1$ は除かれる。残りは $15-10-6-3-13-12-4-5-11-14-2-7-9$ という $13$ 頂点の道になり、その最大独立集合の大きさは $\lceil 13/2\rceil =7$ である。合わせて $1+7=8$。）

よって、独立集合の要素の個数の最大値は $8$ である。

$i+j\le 14+15=29$ なので、平方数は $4,9,16,25$ のみ。辺は
和 4: $\{1,3\}$
和 9: $\{1,8\},\{2,7\},\{3,6\},\{4,5\}$
和 16: $\{1,15\},\{2,14\},\{3,13\},\{4,12\},\{5,11\},\{6,10\},\{7,9\}$
和 25: $\{10,15\},\{11,14\},\{12,13\}$
の 15 本。

構造: 5 サイクル $1-3-6-10-15-1$ があり、頂点 1 に葉 8 が付き、頂点 3 から道 $3-13-12-4-5-11-14-2-7-9$（3 の先に 9 頂点）が伸びている（頂点数 15、辺数 15 で連結）。

最大独立集合を、頂点 3 を含むかどうかで場合分けする。
(i) 3 を含む: 1,6,13 は除外。残りの道 $12-4-5-11-14-2-7-9$（8 頂点）から最大 4、サイクルの残り $10,15$ は隣接するので 1、葉 8 は 1 が除外なので 1 つ。合計 $1+4+1+1=7$。
(ii) 3 を含まない: 道 $13-12-4-5-11-14-2-7-9$（9 頂点）から最大 5。残りは道 $6-10-15-1-8$（5 頂点）で最大 3（例: 6,15,8）。合計 $5+3=8$。

よって最大は 8。
検算: 集合 $\{2,4,6,8,9,11,13,15\}$ について、任意の 2 つの和を調べると 6,8,10,11,12,13,15,17,19,20,21,22,23,24,26,28 等で、4,9,16,25 のいずれにもならない（例: $2+4=6$, $2+6=8$, $2+8=10$, $2+9=11$, $4+9=13$, $9+15=24$, $11+13=24$, $4+13=17$, $2+13=15$, $9+11=20$）。独立集合である。