Tümevarımı biraz daha farklı biçimde uygulayarak yapılan bir başka ispatı paylaşabilirim.
İspat:
∙ (Başlangıç basamağı)
n=1 durmunda çizge yalnız bir noktadan oluşur ve hiç kenar içermediği için kenar sayısı
n−1=1−1=0 özelliğini sağlamaktadır.
∙ (Tümevarım basamağı)
0<r<n aralığındaki her
r pozitif tam sayısı için
r köşeli ağaç çizgelerinin
r−1 kenara sahip olduğunu kabul edelim.
∙ (İspat basamağı)
n>1 köşeli bir
T ağacını göz önüne alalım.
T ağacının bir
e kenarını seçelim ve bu kenarı silelim. Fakat kenarın uç noktalarını silmeyelim. Böylece
T−e çizgesi ile, bağlantısız iki küçük ağaç elde etmiş olduk. Bunlardan birinin
n1 köşesi, diğerinin de
n2 köşesi olsun. Elbette
n1+n2=n dir. Tümevarım hipotezi gereğince bu küçük ağaçların sırasıyla
n1−1 ve
n2−1 tane kenarı vardır. Sildiğimiz
e kenarını da hesaba katarak
T ağacının kenar sayısını bulabiliriz:
(n1−1)+(n2−1)+1=(n1+n2)−1=n−1
elde edilir. Göstermek istediğimiz de buydu.