低基底定理
1936年、デネス・ケーニヒは局所有限な無限グラフは無限道を持つことを示した。これはケーニヒの補題として知られている。系として有限分岐な無限木は無限枝を持つことが従う。これもケーニヒの補題と呼ばれる。これよりも弱い主張「任意の無限二分木は無限枝を持つ」は弱ケーニヒの補題と呼ばれる。これらの定理の証明には選択公理(より正確には従属選択公理やその弱形)が使用されており、その意味で非構成的である。(ただし、木を構成する各ノードが自然数でラベル付けられている場合、すなわち木が N < ω {\displaystyle \mathbb {N} ^{<\omega }} の部分集合として構成されている場合には、選択公理は不要である。)また、無限枝を再帰的に延長していく際に、「子ノードの中で無限部分木になっている側を選ぶ」という操作が必要となるが、この無限性の判定は非実効的である。
スティーヴン・コール・クリーネは弱ケーニヒの補題の計算可能バージョンが成立しないことを証明した(Kleene 1952)。すなわち、計算可能な無限二分木であって、計算可能な無限枝を持たないものを構成した。ここで構成されている木はクリーネ・ツリーと呼ばれることがある。