$n +1$ köşeli bir ağacın içinde $n$ köşeli bir ağaç vardır

Question

Dün yürürken kanıtlamaya çalıştım ama beceremedim.

Comments

$n+1$ köşeli bir ağacın $n$ köşeli bir alt ağacının bulunması gerektiği bana çok açık geldiğinden bir kanıt gerektiğini düşünmedim. Üst ağacın var olması alt ağaca bağlı zaten diye düşündüm.

---

1 den fazla kosesi olan her agacin en az bir tane yapragi vardir. yapragi agactan uzaklastirirsak agac hala agac kalmaz mi ?

---

@alpercay bence de öyle ama sadece tanımdan hareketle bunu kanıtlamak kolay mı?

@eloi ben de o yönde gitmek istedim ama ilk cümleni nasıl kanıtlarsın?

---

Bu arada ben sadece beyin jimnastiği olsun diye sordum soruyu, yoksa ilgili kanıt ile ilgili bir sıkıntım yok.

---

Yaprak nasıl tanımlanıyor? Bilmediğimden soruyorum.

---

Sanıyorum bir ağaçta sadece bir komşusu olan köşe.

---

O zaman yaprak tanımınıza ve eloinin ilk cümlesine göre 1 den fazla köşesi olan ağacın en az bir kenarı olacağından en az 1 değil de en az 2 yaprağı olmalıdır. Yani en az bir kenarı olan ağacın en az 2 yaprağı olmalı diye düşünüyorum.

---

Ağaç tanımı (Lokman Gökçe'nin sorduğu soruda verildiği haliyle) her bir köşesi arasında bir ve yalnız bir patika olan çizge. Sadece bu tanımdan nasıl görüyoruz bir yaprağın varlığını?

Neden her köşesinin en az iki komşusu olan bir ağaç olamaz?

---

Sanıyorum son cümlenin cevabı ağaç tanımıyla ilgili Özgür hocam; ağaç döngü içermez diyor ya tanımda.

---

Agacin uzerindeki en uzun yolu alalim. Baslangici ve bitisi yaprak olmak zorunda?

Degilse elimizde ya bir dongu var ve cizge agac degil yada en uzun yolu secmemissiniz uzatabilirsiniz yolunuzu ?

---

@ Ozgur ya  sonsuz binary agacin her kosesinin iki komsusu var. Demek ki her agacin en az bir yapragi vardir onermesi sadece sonlu cizgeler icin gecerli

Answer 1

Köşe sayısı $1$ den büyük olan ağaç çizgede derecesi $1$ olan en az iki köşe vardır teoreminden dolayı, derecesi $1$ olan bir $A$ köşesini göz önüne alalım. $A$ köşesi, $C$ köşesi ile bağlantılı olsun. Ağaç çizgeden $AC$ kenarını ve $A$ köşesini silelim, fakat $C$ köşesini silmeyelim. Böylece geriye kalan çizge, $n$ köşeye sahip olan bir ağaçtır.