§C5.3極端原理

証明.$P$の二点からなる部分集合は有限個で少なくとも一つあり、それぞれの点対の距離は正であるから、距離が最小となる点対$A,B$を選ぶことができる。

$P$の点$C$が線分$AB$の内部にあると仮定する。このとき$AC>0$、$CB>0$かつ$AC+CB=AB$であるから、$AC<AB$かつ$CB<AB$である。これは$AB$が$P$の相異なる二点間の最小距離であることに反する。したがって、線分$AB$の内部には$P$の点が存在しない。▨

証明.$V$は空でない有限集合であるから、次数が最大となる頂点が存在し、その次数を$\Delta$と書くことができる。各辺は相異なる二端点の次数へ一回ずつ数えられるので、全頂点の次数の和は$2|E|$である。すべての頂点$u\in V$に対して$\deg(u)\leq\Delta$であるから、

を得る。▨

証明. 主張の反例が存在すると仮定し、反例全体の集合を$C$とする。$C$は自然数の空でない部分集合であるから、最小元$n$をもつ。

$n$が素数ならば、$n$自身が一個の素数の積であるから$n$は反例ではない。したがって$n$は合成数であり、$n=ab$かつ$1<a<n$、$1<b<n$を満たす自然数$a,b$が存在する。$n$の最小性により$a$と$b$は反例ではないので、どちらも有限個の素数の積に分解することができる。それら二つの積を合わせれば$n=ab$も有限個の素数の積に分解することができ、$n\in C$に反する。ゆえに反例は存在しない。▨

証明. 奇数全体の集合$\{1,3,\ldots,2n-1\}$は連続する二整数を含まず、要素数は$n$である。したがって最大値は$n$以上である。

連続する二整数を同時に含まない部分集合を$A=\{a_1<a_2<\cdots<a_k\}$とする。$a_1\geq1$であり、各$i<k$に対して$a_{i+1}\geq a_i+2$である。これらの不等式から帰納的に$a_i\geq2i-1$を得る。とくに$2k-1\leq a_k\leq2n$であるから、整数$k$は$k\leq n$を満たす。よってすべての$A$の要素数は$n$以下であり、先の構成と合わせて最大値は$n$である。▨