Proposisi 2.2.4.

Setiap pohon dengan sedikitnya dua simpul memiliki sedikitnya dua simpul berderajat satu.

Bukti.

Kita memberikan pembuktian dengan kontradiksi. Misalkan \(T\) merupakan pohon dengan sedikitnya dua simpul, dan andaikan, bertentangan dengan pernyataan yang hendak dibuktikan, bahwa tidak terdapat dua simpul berderajat satu.
Misalkan \(P\) merupakan lintasan terpanjang yang mungkin dalam \(T\text{.}\) Misalkan \(u\) dan \(v\) merupakan kedua ujung lintasan tersebut. Karena \(T\) tidak memiliki dua simpul berderajat satu, sedikitnya salah satu dari kedua ujung ini harus berderajat dua atau lebih. Misalkan simpul tersebut adalah \(u\text{.}\) Kita mengetahui bahwa \(u\) bertetangga dengan suatu simpul pada lintasan \(P\text{,}\) tetapi simpul itu juga harus bertetangga dengan simpul lain; sebut simpul tersebut \(u'\text{.}\)
Di manakah \(u'\text{?}\) Simpul tersebut tidak mungkin merupakan simpul pada \(P\text{,}\) sebab jika demikian, akan terdapat dua lintasan berbeda dari \(u\) ke \(u'\text{:}\) sisi di antara keduanya dan bagian awal \(P\) (hingga \(u'\)). Namun, \(u'\) juga tidak mungkin berada di luar \(P\text{,}\) sebab jika demikian, akan terdapat lintasan dari \(u'\) ke \(v\) yang lebih panjang daripada \(P\text{,}\) padahal lintasan semula memiliki panjang maksimum.
Kontradiksi ini membuktikan bahwa harus terdapat sedikitnya dua simpul berderajat satu. Bahkan, kita dapat mengatakan lebih banyak: \(u\) dan \(v\) keduanya harus berderajat satu.
dalam konteks