Ağaç Çizgenin Kenar Sayısı {Çözüldü}

[Lokman Gökçe]

Problem: $n\geq 1$ köşeli (noktalı) bir ağaç çizgenin $n-1$ kenarı vardır, kanıtlayınız.


Not: Bağlantılı olup döngü içermeyen çizgelere ağaç denir. Ağaç çizge ile ilgili buraya bakılabilir.

[alpercay]

Bilmediğim bir konu fakat kanıt tümevarımdan yapılır sanırım:

$n=1$ için ağaç çizge bir nokta ve sıfır kenardan , $n=2$ için iki nokta ve bunları birleştiren bir yoldan (kenar) ibaret olduğundan iddia doğru. $n\gt 2$ için  $n$ köşeli ağaç çizgenin $n-1$ kenarı olsun. Şimdi $n+1$ köşeli bir ağaç çizgenin $n$ kenarı olduğunu söyleyebilirsek kanıt tamamdır. Bu ağaç çizgenin içinde $n$ köşeli bir ağaç çizge bulunur ve kabülümüze göre $n-1$ kenarı vardır. Bu çizgeden $n+1$ köşeli ağaç çizgeye geçebilmek için $n$ inci  köşesini $n+1$inci köşeye birleştirmek gereklidir ve bunun için $1$ kenara ihtiyaç vardır. O zaman $n+1$ köşeli bir ağaç çizgenin $$n-1+1=n$$ kenarı vardır.

[Lokman Gökçe]

Tümevarımı biraz daha farklı biçimde uygulayarak yapılan bir başka ispatı paylaşabilirim.
 

İspat:

$\bullet$ (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.

$\bullet$ (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.

$\bullet$ (İ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 $n_1$ köşesi, diğerinin de $n_2$ köşesi olsun. Elbette $n_1 + n_2 = n$ dir. Tümevarım hipotezi gereğince bu küçük ağaçların sırasıyla $n_1 - 1$ ve $n_2 - 1$ tane kenarı vardır. Sildiğimiz $e$ kenarını da hesaba katarak $T$ ağacının kenar sayısını bulabiliriz:

$$(n_1 - 1) + (n_2 - 1) + 1 = (n_1 + n_2) - 1 = n - 1$$

elde edilir. Göstermek istediğimiz de buydu.