グラフ理論の問題

質問

グラフ理論の問題で分からないものがあります。
次の問題の答えがわかる方は、解答を教えてください。

単純グラフG＝(V,E)で、分離度ｋ＝１のとき、｜V｜＝ｐ、｜E｜＝ｑであるなら、
次の式が成り立つことを証明せよ。
　　ｐ－１＜＝ｑ＜＝(１／２)×ｐ×(ｐ－１)

よろしくお願いします。

回答No.1

nagata

分離度1というのは全ての頂点が連結していると言うことでしょうか。
だとするとほぼ自明のような気がしますが。

厳密にやりたいというのなら帰納法を使えばよいでしょう。
とりあえずpー1＜＝qだけについてやってみます。

p＝1の時 pー1＜＝qは成り立つ。
p＜kの時 pー1＜＝qが成り立つと仮定すると p＝kの時

Gのある頂点vとそれに付随する辺を取り去ったグラフをG'とする。
vの次数をnとするとGが連結グラフなのでG'は高々n個の連結成分に分かれる。
その連結成分をr1,r2,,,rm(m<=n)と置き、各連結成分の頂点数をp1,p2,,pm、
各連結成分の辺数をq1,q2,,,qmと置く。

G'の頂点数はkー1なので
p1+p2+、、、+pm=k-1ーー(*)

また各rは連結グラフで頂点数がk-1以下なので帰納法の仮定よりpi-1<=qiが成り立つ。
(*)に代入すると
(q1+1)+(q2+1)+,,,(qm+1)>=k-1
q1+q2+,,,+qm+m>=k-1(**)
ここでGの辺の数は各連結成分の辺の数と頂点vから出ている辺の数の和なので
q=q1+q2+,,,+qm+n
となります。
よって
q=q1+q2+,,,+qm+n>=q1+q2+,,,+qm+m>=k-1=p-1

以上よりｐ－１＜＝ｑは成り立つ。

てな感じです。
分離度の定義が違ったらごめんなさい。

お礼

ありがとうございます
参考になりました