ryamadaのコンピュータ・数学メモ

完全グラフを重ねながら大きくする

グラフ完全グラフ

頂点数 $k$ の完全グラフでは、すべての頂点ペア間に辺がある
辺の数は $\frac{k(k-1)}{2}$ である
今、頂点数 $k$ の完全グラフが２つあるとする
この２つの完全グラフは $k-1$ 個の頂点が共通であるとする
その共通な $k-1$ 個の頂点は完全グラフになっている
今、このような重なりのある２つの完全グラフの頂点数と辺の数を考える
頂点数は $k+k-(k-1)=k+1$ である
辺の数は $\frac{k(k-1)}{2}+\frac{k(k-1)}{2}-\frac{(k-1)(k-2)}{2}=\frac{(k-1)(k+2)}{2}$ である
ここで、頂点数 $k$ の２つの完全グラフにある、相手の完全グラフに含まれない頂点１個ずつを取り出す。この頂点ペアには辺が引かれていないので、これに辺を引く
すると、辺の数は $\frac{(k-1)(k+2)}{2}+1=\frac{k^2+k-2+2}{2}=\frac{k(k+1)}{2}$ となる
頂点数は $k+1$ であるから、これは、頂点数と辺の数から、頂点数 $k+1$ の完全グラフになっていることがわかる