😽
グラフ: 少なくとも2つの頂点を持つすべてのグラフでは、同じ次数を持つ少なくとも2つの頂点があることの証明
𝑛個の頂点を持つグラフでは、拡張点は次数としては{0,1,2、…、𝑛-1}をとりえる。
ここで、𝑛個の頂点を持つグラフには、次数0の頂点と次数𝑛-1の両方を含めることはできない。なぜなら、次数𝑛-1の頂点𝑣があると仮定すると。次に、𝑣はそれ以外の頂点と全て辺を持つことになる。したがって、その場合、次数0の頂点は存在しない。
nこの頂点を持つグラフでは、頂点の次数の集合は以下のいずれかである。
- {1,2,3,4,…𝑛−1}
- {0,1,2,3,…𝑛−2}
いずれの場合も、次数はn-1個のパターンがある。
頂点がn個で、各々の頂点の次数がn-1通りなので、鳩の巣原理より、少なくとも2つの頂点は同じ次数となる。
Discussion