次数シーケンスによって平面グラフを生成できるかどうかを判断するにはどうすればよいですか？
次のグラフの次数シーケンスの場合、
$2,2,2,3,3,3,3,4,5,5\\1,1,1,1,2,2,2,2,3,3$
接続され平面である単純な無向グラフの次数シーケンスはどれですか？
2番目のものだけが有効なシーケンスになると思います。次数シーケンスが平面グラフを生成できるかどうかを判断するための一般的なルールはありますか？
回答
一般に、次数シーケンスが平面グラフのシーケンスであるかどうかについて、ある程度の考慮が必要になります。たとえば、クラトフスキの定理、またはよく知られているエッジバウンドの使用を含むいくつかの可能な戦略については、この質問を参照してください$3n - 6$。平均次数を計算することもできます。平面グラフの場合、厳密に6未満である必要があります（平面基準を参照）。グラフがいずれかの基準に違反しているかどうかを確認するために、多くの時間をチェックします。
両方のシーケンスは平面グラフを表す場合があります。
にとって $2,2,2,3,3,3,3,4,5,5$、あなたはいくつかのことに気付くかもしれません。仮定しているので$G$ つながっている、 $G$ 木になることはできません（程度はありません $1$頂点）、したがってサイクルがあります。しかしながら、$|E(G)| = 16 \le 3(10) - 6 = 24$、だから運がない（覚えておいてください、グラフが非平面であることを証明するためにこの境界を使用することしかできません。）おそらく、遊んだ後、平面グラフがあると思うかもしれません、そしてあなたは正しいでしょう。Havel--Hakimiアルゴリズムを使用して、パスの次数シーケンスを取得したらすぐに停止します。$8$ 頂点については、次のグラフがあります。
この例から、必ずしもそうとは限らないことがわかります。 $G$ サイクルはありますが、三角形はありません（これにより、の改善された境界を使用できるようになります $2n-4$）。その時でさえ、$|E(G)| = 16 = 2(10) - 4$。
にとって $1,1,1,1,2,2,2,2,3,3$、このグラフには含めることができないことがすぐにわかります $K_5$ または $K_{3,3}$細分化として、したがって平面でなければなりません。これはクラトフスキの定理を使用しています。また、この次数シーケンスを持つツリーを見つけるのはそれほど難しいことではありません。
最初のシーケンスでは、すぐに気付くかもしれません $G$ 持つことはできません $K_5$ ただし、細分化 $K_{3,3}$より多くの推論が必要な場合があります。つまり、2番目のシーケンスとは異なり、最初のシーケンスが平面グラフを表すことができることを示しましたが、そうである必要があることは示していません。