２−２−２．ダイアモンド図形

■ダイアモンド図形は，その図形をグラフに埋め込むことによって，必ずそのグラフを非ハミルトングラフとしてしまうようなある特殊な図形クラスである．ハミルトン通路およびダイアモンド図形は前節に既出しているが，ここで厳密な定義を与える．

定義2-2-2.1: ハミルトン通路

必ずしも連結でないグラフＧのすべての点を通る互いに疎なパス集合（長さ０のパス，つまり点を含む）をＰとする．Ｇの真部分点集合ＳがＰのパスのすべての端点を含むとき，ＳはＧのハミルトン通路Ｐを持つという．

定義2-2-2.2: ダイアモンド図形

必ずしも連結でないグラフＤの真部分点集合Ｓがハミルトン通路を持たないとき，グラフＤはＳを接合部とするダイアモンド図形であるという．

連結なグラフＧの真部分グラフＤがダイアモンド図形であり，Ｄが接合部ＳによってのみグラフＧに連結しているとき（Ｓの点を除去することによって，グラフＧがＤとそれ以外の部分に分割されるとき），「ダイアモンド図形ＤはグラフＧに埋め込まれている」という．

■ハミルトン通路はグラフＧの全域パス集合であり，ダイアモンド図形とはＧのある部分点集合Ｓがハミルトン通路を持たないようなグラフである．特に，任意の偶サイクルは，サイクル上の点を１つ置きに取った点集合を接合部とするダイアモンド図形である．

定理2-2-2.1: ダイアモンド図形の埋め込み

グラフＧの真部分グラフＧｄがダイアモンド図形であり，ＧｄがＧに埋め込まれているとき，グラフＧは非ハミルトングラフである．

証明: ダイアモンド図形の定義により明らか．

定理2-2-2.2: 非ハミルトングラフの完全部分グラフ

非ハミルトングラフＧが完全部分グラフＫを持つとき，グラフＧはＫを接合部とするダイアモンド図形である．特に，Ｇの隣接する２点をｘ，ｙとするとき，グラフＧは｛ｘ，ｙ｝を接合部とするダイアモンド図形である．

証明: ダイアモンド図形の定義により明らか．

■すべての非ハミルトングラフにはダイアモンド図形が（真部分集合として）埋め込まれていると言えるだろうか？答えはおそらく否定的である．たとえば，メッシュグラフのようなグラフでは，グラフのある特定の部分を取り出してダイアモンド図形であると示すことはできないと考えられる．おそらく非ハミルトングラフは，内部にダイアモンド図形を持つクラスとそうでないクラスの２種に区分されると考えてよいだろう．

■グラフの内部に埋め込まれたダイアモンド図形を効率的に検出する方法は現在のところ発見されていない．この問題の難しさは，ｋ端子分割検定の計算量が最悪指数オーダーになることと同等であると想定される．