グラフ理論の問題について

質問

グラフ理論についての質問です。よろしくお願いします。

「グラフGが正則でdiam(G)=3ならば、diam(~G)=2である」（~GはGの補グラフです）
を証明したいです。
前の設問に「diam(G)≧3ならばdiam(~G)≦3」というのがあるので（これは証明できました）、diam(~G)=1あるいはdiam(~G)=3の場合に矛盾を導く方向で考えています。
diam(~G)=1とするとGが空グラフになってしまう、というのは分かるのですが、diam(~G)=3の場合に矛盾を導くところが上手くいきません。
どのような方針で話を進めていけば良いのか、あるいはストレートにdiam(~G)=2を示すもっとスマートな方法があるのか、ご教示いただければ幸いです。

回答No.3

stomachman

No.2のタイプミス修正です。
>　　∃p∃q∀x(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (￢(p*x) ∨ ￢(q*x)))
と
>　　∃p∃q∀x(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (p.x ∨ q.x)))
は

　　∃p∃q(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (￢(p*x) ∨ ￢(q*x)))
と
　　∃p∃q(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (p.x ∨ q.x)))
でなくちゃ。

回答No.2

stomachman

スマートなやり方はどうも思いつきませんで、もっちゃりしてますけど。
　正則次数Δ≧2の連結で正則なグラフGの直径がdiam(G)=3で、しかもdiam(~G)＞2だと仮定して矛盾を示しちゃどうでしょうか。
　以下、ノードa,bがG上で隣接している(edgeで繋がっている)ことをa.bと書く事にし、Gのノードの集合を（めんどくさいから）Gと書く事にします。
　また、ノードa,bが~G上で隣接していることをa*bと書くことにすると、diam(~G)＞2とは
　　∃p∃q∀x(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (￢(p*x) ∨ ￢(q*x)))
ってことですが、補グラフってのは a.b ⇔ ￢(a*b) という意味なのだから、
　　∃p∃q∀x(p∈G ∧ q∈G ∧ p≠q ∧ ∀x(x∈G ⇒ (p.x ∨ q.x)))
である。そのようなp, qを固定します。すると（x=pとかx=qの場合を考えれば明らかに）p.qですね。そして、p, q以外のノードの集合 H = G＼{p, q} を
　　P = {x | x∈H ∧ x.p ∧ ￢(x.q)}
　　Q = {x | x∈H ∧ x.q ∧ ￢(x.p)}
　　R = {x | x∈H ∧ x.p ∧ x.q}
と分類します。pもqも枝がΔ本出ているけれども、そのうちの1本の枝はp.qに使ってますから、
　　|P∪R| = |Q∪R| = Δ-1
です。( |X|は集合Xの要素の個数(濃度)のことです。）
　さて、もし
　　∀x(x∈P → ∃t(t∈Q ∧ x.t)) ∧ ∀x(x∈Q → ∃t(t∈P ∧ x.t))
なら、明らかにdiam(G)≦2。なのでその否定
　　∃x(x∈P ∧ ∀t(t∈Q → ￢(x.t))) ∨ ∃x(x∈Q ∧ ∀t(t∈P → ￢(x.t)))
が成立つと分かります。これを場合分けします。
　∃x(x∈P ∧ ∀t(t∈Q → ￢(x.t)))の場合、このノードx∈Pについて、p以外のお隣さんノードΔ-1個は(P∪R)＼{x}の中から選ばれなくてはなりませんが、|(P∪R)＼{x}| = Δ-2 だからこれは無理。∃x(x∈Q ∧ ∀t(t∈P → ￢(x.t))) の場合も同じです。

回答No.1

graphaffine

解答が無いようなので、部分的ではありますが、投稿させてもらいます。

Gの正則次数(Δとする)で場合分けする。
(i)Δが0または1の場合)精密に言うには、不連結の場合も含めた直径の定義を知りたいところですが、ともかくdiam(G)=3になり得ないのは明らかですから、題意は自明的に成立する。

(ii)Δが2で連結の場合)この場合、diam(G)=3となるのは、Gが7-サイクルのときのみ。このとき~Gは4-正則。
diam(~G)=2を示すには、~Gの隣接しない2点a、bが~Gにおいて共通隣接点を持つことを示せばよいが、このことは正則次数が4であることから、部屋割り論法で分かる。

他の場合は検討中ですが、このやり方が方針的に正しいかどうかは不明。なお、
>「diam(G)≧3ならばdiam(~G)≦3」というのがあるので（これは証明できました）
であれば、その証明を記載してもらえればそれがヒントになったかもしれない。長いのならば概略でもよいので。

補足

ご回答ありがとうございます。
正則次数に注目する方法ですね。考えてみようと思います。

＞不連結の場合も含めた直径の定義

非連結の場合、異なる連結成分にある2頂点間の距離は無限大で定義しているので、直径も無限大となります。

＞diam(G)=3となるのは、Gが7-サイクルのときのみ

Gが6-サイクルの場合もdiam(G)=3になりませんでしょうか？

＞「diam(G)≧3ならばdiam(~G)≦3」の証明

u,vをd(u,v)=diam(G)となる頂点とし、wをu,v以外の頂点とすると、d(u,v)≧3よりGにおいて
・uとvは非隣接
・u,vのうち少なくとも一方はwと非隣接
が成り立つので、~Gにおいて
・uとvは隣接
・u,vのうち少なくとも一方はwと隣接
が成り立ち、u,v以外の任意の2頂点w1,w2に対して
・d(u,v)=1
・d(u,w)=1（uとwが隣接）or 2（uとwが非隣接→vとwが隣接）
・d(v,w)=1（vとwが隣接）or 2（vとwが非隣接→uとwが隣接）
・d(w1,w2)=1（w1とw2が隣接）or 2（w1とw2が非隣接かつw1とw2がu,vの同じ頂点と隣接）or 3（w1とw2が非隣接かつw1とw2の一方がuと、もう一方がvと隣接）
となり、どんな2頂点間の距離も3以下となる。

が概要となります。

以上、よろしくお願いします。