K（9、9）の交差数
私はグラフ理論を研究していますが、この問題を解決する方法がわかりません。私はグラフが苦手で、この種の問題を解決するのはかなり難しいです。何か説明をいただければ幸いです。前もって感謝します！
質問：すべてのk接続（$k>1$）ハミルトン閉路を持たないグラフは、を含む閉路を持ちます $k$独立した頂点とその隣人？これはに当てはまることが知られています$k = 2$ そして $3$。たとえば、右のグラフは3接続されていますが、ハミルトンではありません。そして、示されている点線のサイクルには、$3$独立した頂点（色が薄い3つの頂点）とその隣接する頂点。ハミルトンではないことを確認するには、このグラフが完全2部グラフにすぎないことに注意してください。$K(3,4)$。
回答
まず、ケースについて考えてみましょう。 $G$つながっている。場合$|V| < k$、それから私たちは確かに分割することはできません $V$ に $k$ 空でないサブセットなので、仮定しましょう $|V| \geq k$。
この場合、適切なパーティションがあると私は主張します。これを示すには、サブセットを見つけるだけで十分です$V' \subseteq V$ と $|V'| = k-1$ そのような $G - V'$ 接続されています：それから私たちは取ることができます $V_1$ することが $V - V'$ そして私達はすることができます $V'$ それぞれ1つの要素を持つセットに $V_2,\dots,V_k$。どうやってそのようなものを見つけるのですか$V'$？直感的に、私たちはのスパニングツリーを取ります$G$ スナップするまで、葉を1つずつ「スナップオフ」します。 $k-1$。正式には、トラバースできます$G$いくつかのアルゴリズム（DFSなど）によると。しましょう$v_1, \dots, v_n$このトラバーサル中に頂点を訪問する順序になります。この順序で頂点をトラバースできるという事実は、最初の$n-(k-1)$ 頂点は、の接続されたサブグラフを誘導します $G$、だから私たちは取ることができます $V'$ 最後になる $k-1$ 頂点。
仮に $G$接続されていませんか？まあ、それがより多くの接続されたコンポーネントを持っているなら$k$、そのようなパーティションはあり得ません（なぜですか？）。それ以外の場合（$|V| \geq k$）基本的に同じアイデアを使用できます：スパニングフォレストを取る $G$ スナップされたリーフの数と残りの接続されたコンポーネントの数が $k$。繰り返しますが、これはトラバーサル順序を使用して実行できますが、この場合にのみ、スナップオフする必要がある葉の数を決定するためにいくつかの考慮が必要です。