グラフ理論の問題

ハミルトン閉路があることは、閉路を実際に $1$ つ作って示す。ないことは、次の $2$ つの事実のどちらかを使って示す。

(A) ハミルトン閉路 $C$ から頂点を $1$ つ除くと、残りの頂点をすべて通る道になり、つながったまま残る。したがって、ある頂点 $v$ を除いたグラフ $G-v$ が $2$ つ以上の連結成分に分かれるなら、$G$ にハミルトン閉路はない。

(B) 2 部グラフでは、閉路の辺は必ず $2$ つの部集合を交互に行き来する。したがってハミルトン閉路があるなら、$2$ つの部集合の頂点数は等しい。

$G_1$：頂点 $3$ を除くと、残る辺は $12,45,46,56$ だけである。よって $G_1-3$ は $\{1,2\}$ と $\{4,5,6\}$ の $2$ つの連結成分に分かれる。(A) より、$G_1$ はハミルトン閉路をもたない。

$G_2$：$1\to 2\to 3\to 6\to 5\to 4\to 1$ を考える。使う辺は $12,23,36,65,54,41$ で、どれも辺集合に含まれている。また $6$ 頂点をちょうど $1$ 回ずつ通っている。よって $G_2$ はハミルトン閉路をもつ。

$G_3$：$a,b,c$ を白、$u,v,w,x$ を黒に塗る。$9$ 本の辺はどれも白の頂点と黒の頂点を結ぶので、$G_3$ は部集合 $\{a,b,c\}$ と $\{u,v,w,x\}$ をもつ 2 部グラフである。部集合の大きさは $3\ne 4$ なので、(B) より $G_3$ はハミルトン閉路をもたない。（頂点数 $7$ が奇数であることからも同じ結論になる。）

$G_4$：$1\to 2\to 4\to 6\to 5\to 3\to 1$ を考える。使う辺は $12,24,46,65,53,31$ で、どれも辺集合に含まれている。また $6$ 頂点をちょうど $1$ 回ずつ通っている。よって $G_4$ はハミルトン閉路をもつ。

以上より、ハミルトン閉路をもつのは $G_2$ と $G_4$ であり、答えは $\{2,4\}$ である。

各グラフについて調べる。

$G_1$: 辺 $34$ は橋である（除くと $\{1,2,3\}$ と $\{4,5,6\}$ に分かれる）。閉路は橋を含めないので、ハミルトン閉路はもたない。

$G_2$: 三角柱グラフである。閉路 $1\to 2\to 3\to 6\to 5\to 4\to 1$ を考えると、辺 $12,23,36,65,54,41$ がすべて存在し、全頂点を $1$ 回ずつ通る。よってハミルトン閉路をもつ。

$G_3$: 辺はすべて $\{a,b,c\}$ と $\{u,v,w,x\}$ の間にあり（$x$ の隣接頂点は $a,b,c$）、二部グラフである。両側の頂点数が $3$ と $4$ で異なるので、ハミルトン閉路はもたない（閉路は両側を交互に通るため、両側の頂点数が等しくなければならない）。

$G_4$: 次数 $2$ の頂点 $1,4,5,6$ の辺はすべて閉路に使われる。すなわち $12,13,24,46,35,56$ を使う。閉路 $1\to 2\to 4\to 6\to 5\to 3\to 1$ は全頂点を $1$ 回ずつ通る。よってハミルトン閉路をもつ。

したがって答えは $\{2,4\}$。