つきなみ

$S$ を smallest separating set としたとき、$v \in S$ は $G-S$ の全ての連結成分に辺を伸ばしているから、$N(v,G)$ がハミルトンサイクル $C$ を持っていることを考えると、$S$ には $v$ 以外に少なくとも 2 頂点は必要だから、$|S| \geq 3$ である。

$S = \{v,x,y\}$ としたとき、$G-S$ はちょうど 2 つの連結成分 $H_1, H_2$ を持つ。($C-\{x,y\}$ が 2 つの連結成分からなっているから)、そして、$x,y$ は $v$ の近傍でなければならない。$x$ についても同様に考えると、$y,v$ は $x$ の近傍でなければならない。つまり$xyz$ は 3 サイクルである。また $xy$ は $C$ のコードであり、ハミルトンサイクルの辺ではない。

$G$ が局所ハミルトニアンであることと $v,x,y$ が 3 サイクルをなしていることから $G-H_i$ も局所ハミルトニアンであることがわかる $(i=1,2)$。

triangulation なら 1 を満たすことは自明。さらに $G$ の辺は 2 つの 3-facial サイクルに含まれており、定理 5.1.5 からそのサイクルは nonseparating である。それ以外の nonseparating 3-cycle に含まれているとするとそれは noncontractible だから、矛盾する。

逆に、1, 2 を満たすとする。任意の $v \in V(G)$ は以下の条件を満たすハミルトンサイクル $H_v = v_0v_1...v_{d-1} (d = \text{deg}(v))$ をただ一つもつ: $v$ を含む nonseparating 3 サイクルの集合と $vv_iv_{i+1} (i=0,...,d-1)$ が一致する。

このサイクル $H_v$ を $v$ の rotation $\pi_v$ とする。適切に辺の符号を決めれば (下のように rotation が一致していないときに - をつけて、そうでないときに + をつける)、facial walk が nonseparating 3 サイクルであるような triangulation になる。

ハミルトンパス → 局所ハミルトニアン: 元々 $G$ に存在していた頂点 $v$ については 3 正則だから、新しく足した 3 頂点を使えば、近傍にハミルトンサイクルが得られる。新しく付け足した頂点 ($v_1,v_2,v_3$ とする)については $G$ のハミルトンパスを $P$として ( $G$ に含まれる $P$ ) → $v_2$ → ($G$ のコピーに含まれる $P)$ → $v_3$ の順に回れば $v_1$ の近傍のハミルトンサイクルが得られる。$v_2, v_3$ も同様。

局所ハミルトニアン → ハミルトンパス: 上と同様

$\overline{N}(v,G)$ が 3 連結で平面的だから、その平面描画で $v$ を取り除いてできた $N(v,G)$ (2 連結) の面の facial cycle がハミルトンサイクルになっている。

逆に $G$ が局所ハミルトニアンであったとする。$v \in V(G)$ をとって、$C=v_1v_2...v_d$ を$N(v,G)$ のハミルトンサイクルとする。定理 5.3.1 (separating set $vxy$ について、$v$ の近傍のハミルトンサイクルには辺 $xy$ は含まれない) より $v$ と $C$ の辺を使った 3 角形は nonseparating である。

下の図のように $C$ を凸多角形、$v$ を $C$ の外側に描く。$N(v,G)$ に存在している $C$ のコードを全て内側に直線で描く。この埋め込みが $\overline{N}(v,G)$ の平面への埋め込みになっていることを示す。$v_iv_j$ と $v_sv_t$ が交わっているとすると、辺 $vv_i$ はすでに $vv_{i-1}v_i$ と $vv_iv_{i+1}$ という nonseparating 3 サイクルに含まれているから性質 2 を満たすという仮定より $vv_iv_j$ は separating でなければならない。$G$ は命題 5.3.1 より 3 連結であるから、Menger の定理より$G$ の任意の頂点 $z$ $\not \in N(v)$ と $v$ の間に 3 本の disjoint なパスをもつ。このことから $N(v)-\{v_i,v_j\}$ のある頂点から $z$ へ伸びるパスが存在する。よって、$G-\{v,v_i,v_j\}$ において、$C-\{v_i,v_j\}$ の 2 つのパスが辺 $v_sv_t$ で結ばれていることを考えると、$G-\{v,v_i,v_j\}$ は連結である。これは $vv_iv_j$が separating であったことに矛盾する。

$G$ が 1 を満たすとする。$\Pi'$ が $\Pi$ と同じオイラー種数を持つ埋め込みとする。同じオイラー種数を持つことから $\Pi'$ もまた triangulation である。よって全ての $\Pi'$-facial 3 サイクル $C$ が $\Pi$-facial でもあることを示せば良い。命題 5.3.1 ($v$ の近傍のハミルトンサイクルに含まれる辺 $xy$ があると $vxy$ は nonseparating である) より $C$ は nonseparating である。よって条件 1 より $C$ は $\Pi$-contractible である。よって $C$ は $\Pi$-facial である。つまり $\Pi=\Pi'$ が成り立つ。

$G$ が 2 を満たすとする。$G$ の $\Pi$-noncontractible な 3 サイクル、induced $\Pi$-noncontractible な 4 サイクルに含まれる辺に次数 2 の頂点を一つ加えて subdivide する。できたグラフ $G'$ は edge-width が 5 以上で、全ての facial cycle の長さが 4 以下である。

よって LEW である。定理 5.2.2 を使う。