(Burak VARICI)
Bunu mümkün kılan en küçük $k$ sayısı $26$ dır.
$80$ kentimizi $80$ köşeli bir grafın köşeleri ve karşılıklı uçak seferlerini de bu köşeler arasındaki yönlü kenarlar olarak düşünelim. $k$ aktarma ile, yani grafımızı düşünürsek en fazla $k+1$ kenar üzerinden herhangi bir köşeden başka bir köşeye her zaman ulaşılmasını sağlayan en küçük $k$'yı arıyoruz. Ayrıca her köşenin derecesinin en az $7$ olduğunu biliyoruz.
Öncelikle $k=26$ aktarma için bir örnek verelim: $K_{m} $ ile $m$ köşeli bir complete grafı gösterelim. Eğer her $v_{1} \in K_{i} $, $K_{j} $deki köşelerden her birine direkt bağlı ve her $v_{2} \in K_{j} $, $K_{i} $ deki köşelerden her birine direkt bağlı ise bu durumu $K_{i} \leftrightarrow K_{j} $ ile gösterelim. Dolayısıyla eğer $K_{i} \leftrightarrow K_{j} $ ise bu $i+j$ köşe bir $K_{i+j} $ oluşturur.
Grafımız şu şekilde olsun: $\underbrace{K_{5} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \dots\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{5} }_{8 \text{ Köşe} }$ Aradaki $K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} $ üçlülerinden $8$ tane olsun. Dolayısıyla toplamda $80$ köşe vardır ve her köşenin derecesi en az $7$ dir.
Diğer taraftan en soldaki $K_{5} $ teki bir köşeden başlarsak, en sağdaki $K_{5} $ e en az $27$ kenar üzerinden yani $26$ aktarma ile gidebiliriz. Ayrıca bu grafta belirtilen kenar bağlantıları dışında bir kenar da olmasın. Şimdi $27$ nin maksimum olduğunu ispatlayalım.
Grafımızı bir ağaç şeklinde ifade edeceğiz. Bir $V$ köşesi seçelim ve ağacın en tepesine koyalım. $V$ nin bir alt katmanına $V$ nin direkt bağlı olduğu köşeleri yerleştirelim. Ondan sonra gelen her $k.$ katmana, $1,2,..,(k-1).$ katmanlarda bulunmayan ve $(k-1).$katmandaki köşelerden en az birine direkt bağlı olan köşeleri yerleştireceğiz. Grafımızın sonlu sayıda köşesi olduğundan, sonlu sayıda katman yer alır.
Toplam
m katman olsun. $t.$ katmanda da $a_{t} {\rm \; }(1\le t\le m)$ alsın. Grafımız bağlantılı olduğundan bu "katmanlandırma'' tüm köşeleri kapsar.
Dolayısıyla $a_{1} +a_{2} +..+a_{m} =80$ ve $l.$ katmandaki bir köşenin direkt bağlı olduğu köşeler sadece $l.{\rm \; ,}(l-1).$ veya $(l+1).$ katmanlarda yer alabilir.
Fakat bir $v_{1} \in l.$katman alırsak, $7\le der(v_{i} )\le (a_{l} -1)+a_{l-1} +a_{l+1} $ olduğundan her $m-1\ge l\ge 2$ için $a_{l-1} +a_{l} +a_{l+1} \ge 8$ olmalıdır.
Ayrıca benzer mantıkla $a_{1} +a_{2} \ge 8$ ve $a_{m-1} +a_{m} \ge 8$ olduğunu söyleyebiliriz. $m\le 28$ olduğunu göstermek istiyoruz, çünkü böylece $V$'den herhangi bir köşeye en fazla $m-1\le 27$ kenar kullanılarak ve dolayısıyla $26$ aktarmada ulaşılmış olacak.
Aksini varsayalım, $m>28$ olsun. Her $r$ için $a_{r} >0$ olduğundan : $$\begin{array}{l}
80=a_{1} +a_{2} + \dots +a_{m} \\
=(a_{1} +a_{2} )+(a_{3} +a_{4} +a_{5} )+\dots+(a_{24} +a_{25} +a_{26} )+(a_{27} +a_{28} +..a_{m-2} ) +(a_{m-1} +a_{m} ) \\
>(a_{1} +a_{2} )+(a_{3} +a_{4} +a_{5} )+\dots+(a_{24} +a_{25} +a_{26} )+(a_{m-1} +a_{m} ) \\
\ge 8+8+ \dots +8=80.
\end{array}$$
Böylece çelişki elde ederiz. Demek ki $m\le 28$ ve dolayısıyla${\rm \; }m-1\le 27$ bulunur.
Dolayısıyla en fazla $26$ aktarma ile istenilen yere ulaşılır. $\triangleright $
