完全グラフを重ねながら大きくする
- 頂点数
の完全グラフでは、すべての頂点ペア間に辺がある
- 辺の数は
である
- 今、頂点数
の完全グラフが2つあるとする
- この2つの完全グラフは
個の頂点が共通であるとする
- その共通な
個の頂点は完全グラフになっている
- 今、このような重なりのある2つの完全グラフの頂点数と辺の数を考える
- 頂点数は
である
- 辺の数は
である
- ここで、頂点数
の2つの完全グラフにある、相手の完全グラフに含まれない頂点1個ずつを取り出す。この頂点ペアには辺が引かれていないので、これに辺を引く
- すると、辺の数は
となる
- 頂点数は
であるから、これは、頂点数と辺の数から、頂点数
の完全グラフになっていることがわかる