ツォルンの補題により全ての連結グラフが全域木を持つことが分かる。部分グラフのうち、木であるものからなる集合は包含関係により順序付けられ、鎖の和集合は上界となる。ツォルンの補題により極大の木が存在する。グラフが連結であるため、これは全域木である。この図のような有限グラフについてはツォルンの補題は不要である。 集合論においてツォルンの補題(ツォルンのほだい、英: Zorn's lemma)またはクラトフスキ・ツォルンの補題(クラトフスキ・ツォルンのほだい)とは次の定理をいう。 命題 (Zorn の補題) 半順序集合Pは、その全ての鎖(つまり、全順序部分集合)がPに上界を持つとする。このとき、Pは少なくともひとつの極大元を持つ。 この定理は数学者マックス・ツォルンとカジミェシュ・クラトフスキに因む。選択公理と同値な命題の一つ。 準備[編集] この補題で使われている用語の定義は以下のとおりである。