ケーニヒの補題
ブラウワーのfan定理は、分離できないbarは一様なbarであることを主張する。
この定理は、barをコンパクト空間 { 0 , 1 } ω {\displaystyle \{0,1\}^{\omega }} の開被覆と見なすことにより示される。 barの要素である列はこの空間の開基であり、これらの開基は空間を被覆する。 コンパクト性により、この被覆は有限部分被覆を持つ。 fan定理の N を有限部分被覆の要素である開基のうち最長列の長さとして取ればよい。 この位相的な証明は、次のケーニヒの補題の変形にも通用する。:任意自然数 k に対し、 { 0 , ... , k } < ω {\displaystyle \{0,\ldots ,k\}^{<\omega }\,} のいかなる無限部分木も無限な道をもつ。
証明にあたって、グラフの含む無限個の各点を vi の形で表し、グラフは連結であるとする。
v1 を任意にとる。グラフの無限個の点が v1 からの単純道で到達でき、 そのような道はいずれも v1 に接続する有限個の点のうちどれかから始まる。 そのような点のうち、その点から無限個の点に v1 を通らない道で到達できるようなものがある (もしそのような点がなかったらグラフの全体が有限集合の有限和であり、グラフが無限であることに反する。) ここで、そのような点を一つとって v2 とする。
今、グラフの無限個の点が v2 からの v1 を通らない単純道で到達できる。 そのような道はいずれも v2 に接続する有限個の点のうちどれかから始まる。 上で行ったのと同様の議論により、無限個の点に到達できる道の始点をとって v3 とする。
同様の議論を続ける数学的帰納法により、無限単純道が得られる。 各ステップで帰納法の仮定は、 vi から始まる一つの単純道で、 ある有限集合を通らずに無限個の点に到達できるということであり、 帰納法の議論は vi をその有限集合に加えてもある隣接点が帰納法の仮定を満たすことにより成り立つ。 同じ点が二度追加されないことも構成法から保証されていて結果として、 任意の n に対して所望の道を成す vn が選べる。
この証明は構成的でないとされることがある。というのは、 各ステップで、無限個の点に到達できる隣接点が存在することを背理法で示してあり、 この補題のcomputational aspectsが、 構成的数学の主流から言って構成的と思える証明が存在しないことを示唆しているからである。