(Eren DURLANIK)
Öncelikle $k\ge 2n-3$ olması gerektiğini ispatlayalım. Kentlerin $K_1,K_2,\ \dots ,\ K_{n-2},\ A,\ B$ olduğu bir ülke alalım. Bu ülkenin ekonomik durumu çok iyi olmasın. Sadece $A$ ile $K_1,K_2,\dots ,\ K_{n-2}$ ve $B$ ile $K_1,\ K_2,\dots ,\ K_{n-2}$ şehirleri arasında ve $A$ ile $B$ arasında yollar yapılmış olsun. Bu ülkede hangi şehir kapanırsa kapansın geriye kalan şehirler kendi aralarında bağlantılıdır.
Eğer $k<2n-3$ olsaydı bu ülkedeki yol sayısı $2n-3$ olduğundan en az bir yolu kendimiz yönlendiremeyecektik. Bu yol $AB$ olsaydı $l=AB$ ve $B\to A$ yönünde olursa istenen sağlanamaz. Bu yol $1\le i\le n-2$ için $AK_i$ olsaydı $l=AK_i$ ve $K_i\to A$ yönünde olursa istenen sağlanamazdı. Bu yol $1\le i\le n-2$ için $K_iB$ olsaydı $l=K_iB$ ve $B\to K_i$ yönü için $A$ dan başlayıp $l$ den geçip $B$ ye her kente en fazla bir kez uğrayarak ulaşamazdık. Yani $A$ kenti $B$ kentine $k-$ yönlü bağlanamazdı. Halbuki ülkenin herhangi iki şehri $k-$ yönlü bağlanabiliyordu. Bu bir çelişki olup $k\ge 2n-3$ olur. Şimdi $k=2n-3$ ün yeterli olduğunu ispatlayalım.
Sorudaki şartları sağlayan bir $G$ ülkesi alalım. $G$ nin herhangi iki $A$ ve $B$ kenti için $A$ kentinin $B$ kentine $(2n-3)-$ yönlü bağlanabilir olduğunu ispatlayacağız. $G$ nin iki $A$ ve $B$ farklı kentlerini alalım. Her şehirden en fazla bir kez geçerek $A$ dan $B$ ye (henüz yollar yönlendirilmemişken) gidebileceğimiz bir $m_1$ yolu alalım. $A$ ve $B$ dışındaki bir kenti silince geriye kalanlar bağlantılı olduğundan $A$ ile $B$ arasında her kentten en fazla bir kez geçen bir yol vardır. Eğer $m_1$ üzerinde olmayan kent yoksa tamam. Diyelim ki $m_1$ dışında kentler var. Bu kentler kümesi $M_1$ olsun. Her kentten en fazla bir kez geçen yollara ``ekonomik yol'' diyelim.
Sadece başlangıç ve bitiş kentleri $m_1$ de olan, $M_1$ den en az bir kent içeren bir ekonomik yol varsa bu ekonomik yol ve $m_1$ yolunun birleşimi $m_2$ olsun. $m_2$ dışındaki kentler kümesi $M_2$ olsun.
Sadece başlangıç ve bitiş kentleri $m_2$ de olan, $M_2$ den en az bir kent içeren bir ekonomik yol varsa bunu da alıyoruz ve bu ekonomik yol ile $m_2$ nin birleşimi $m_3$ olsun.
Bu şekilde ilerleyelim ve ekonomik yolların birleşimi şeklinde son olarak bir $m$ elde edelim. $m$ in dışında kent yoksa tamam. Diyelim ki $m$ nin dışında en az bir kent var. Bunlardan biri $C$ kenti olsun. $B$ yi silince kalan kentler bağlantılı olduğundan $C$ ile $A$ arasında bir ekonomik yol bulunur. O halde $m$ nin dışında kalan kentler kümesine $M$ dersek $C$ den başlayıp $M$ den bazı kentlerden geçerek $m$ deki bir kente ulaşan bir $m^\prime$ yolu olacak. $m^\prime$ yolunun $m$ ile kesişmeden bir önceki şehri $D\ $olsun. ($D=C$ olabilir) $m^\prime$ yolunun $m$ ile kesişen yerdeki şehri $E$ olsun. $E$ yi silince geriye kalan kentler yine bağlantılı olacağından $D$ ile $A$ arasında bir ekonomik yol olacaktır. O halde $D$ ile başlayıp $M$ deki bazı kentlerden geçip $m$ ye $E$ den farklı bir $F$ noktasında ulaşan bir $m^{\prime\prime}$ yolu vardır. Bu yol $DX_1X_2\dots X_sF$ olsun. Bu durumda $EDX_1\dots X_sF$ yolu sadece başlangıç ve bitiş kentleri $m$ de olan ve dışarıdan en az bir kent içeren bir yol olup bu $m$ nin tanımıyla çelişir. O halde $M=\emptyset $ dir.
$A$ dan $B$ ye ulaşan sadece $A$ ve $B$ de kesişen yollar $l_1,\ l_2,\dots ,\ l_s$ olsun. $m_1$ den dolayı $s\ge 1$ dir. Yani böyle en az bir yol vardır.
Oluşturduğumuz tüm kentleri içeren, birkaç ekonomik yolun birleşimi şeklindeki yolları ve şehirleri (yani m yi) alalım. $l_1,\ l_2,\dots ,\ l_s$ $s$ tane ekonomik yoldur. Diğer yollar $i\ne j$ olmak üzere $l_i$ den bir kent ve $l_j$ den bir kent uç kentleri olan ve daha başka en az bir kent içeren yollar, $l_i$ den iki farklı kent uç kent içeren ve daha başka en az bir kent içeren yollar ve bunun bunlar için de tanımlanmış olan şekildeki yollardır. Sadece uç noktaları diğer yollarla kesişen ekonomik yollardan oluşan bir durum elde ettik. Bu yollardan biri $p$ yolu olsun. $p$ nin uç noktaları dışındaki şehir sayısı $a_p$ olursa$p$ deki kenar sayısı $1+a_p$ olur. O halde elde ettiğimiz durumda kenar sayısı $\sum_p{1+a_p}$ olur. $a_p\ge 1$ olup $A$ ve $B$ bu yollardan hiçbirinin içinde (yani ucunda olmayan) bir kent olmadığı için $p$ yollarının sayısı en fazla $n-2\ $dir. $\sum_p{1+a_p=\sum_p{a_p}+\sum_p{1}=n-2+\sum_p{1}\le 2n-4}$ elde ederiz.
En başta seçtiğimiz $m_1$ için $m_1$ i $A$ ve $B$ arasında en az bir köşe içerecek şekilde seçebileceğimizi gösterelim. $A$ ya sadece $B$ bağlı olsaydı $B$ yi silince kalan kentler bağlantısız olurdu. $A$ ile arasında doğrudan yol olan bir $R\ne B$ kentini alalım. $A$ yı silince geriye kalan kentler bağlantılı olup $R$ ile $B$ arasında bir ekonomik yol var ve buna $AR$ yolunu ekleyip bunu $m_1$ seçeriz. $m_1$ den önce de A ile B arasında kenar bulunsaydı onu seçer sonra $m_1$ i seçerdik. Ayrıca $m_1,\ m_2,\ \dots ,\ m$ yi oluşturunca her seferinde sadece uç noktaları $m_i$ de olan en kısa ekonomik yolu alarak ilerleyeceğiz. Bu şekilde elde edeceğimiz son durumda en fazla $2n-4+1=2n-3$ yol bulunur.($AB$ yolunu da saydık)
Şimdi sadece uç noktaları kesişen ekonomik yollardan oluşan yol-kent haritası $H$ olsun. $H$ de uç noktası $A$ olan $AX_1X_2\dots X_s$ yolunu $A\to X_1\to X_2\to \dots \to X_s$ şeklinde yönlendirelim. Uç noktası $B$ olan $Y_1Y_2\dots Y_sB$ yollarını da $Y_1\to Y_2\to \dots \to B$ şeklinde yönlendirelim. Uç noktaları $A$ ve $B$ olan yollar ve $A$ ile $B$ arasındaki kenar $A\to B$ olur. Geriye kalan $Z_1Z_2\dots Z_r$ yollarını $Z_1\to Z_2\to \dots \to Z_r$ şeklinde veya $Z_r\to \dots \to Z_2\to Z_1$ şeklinde yönlendirelim. Kenar sayısı $2n-3$ ten fazla olmadığından bunu yapabiliriz.
Şimdi geriye kalan kenarlar nasıl yönlendirilirse yönlendirilsin herhangi $l$ kenarı için $A$ dan başlayıp $l$ den geçerek $B$ ye ulaşabileceğimizi ispatlayalım. $H$ de ardışık iki köşe (özel durum olarak $A$ ve $B$ (eğer aralarında kenar varsa)) arasındaki kenar $K_1K_2$ seçilirse bu kenarın H de bulunduğu yol $L_1L_2\dots L_sK_1K_2M_1M_2\dots M_r$ olsun. (Yukarıdaki yönlendirmeyi yaparken bir $X_1\dots X_t$ yolunun yönü $X_1\to \dots \to X_t$ ise ($i<j$ olmak üzere) $X_iY_1\dots Y_sX_j$ yolunun yönü $X_i{\to Y}_1\to \dots \to Y_s\to X_j$ olacak şekilde yapacağız)
$p$ nin yönü $L_1\to \dots \to L_s\to K_1\to K_2\to \dots \to M_1\to \dots \to M_r$ olsun. $K_1$ den ters yönde ilerleyecek bir trafik canavarı haritayı oluşturma biçimimizden dolayı $A$ ya, $K_2$ den düz ilerleyen örnek sürücü $B$ ye ulaşacağından $K_1K_2$ den geçip yönlere uyarak $A$ dan $B$ ye ulaşabiliyoruz.
Seçilen $l$ kenarı iki farklı $p$ ve $q$ yolundan $K_1$ ve $K_2$ noktalarıysa ve bunun yönü $K_1\to K_2$ olursa $K_1$ den ters yönde $A$ ya, $K_2$ den düz ilerleyerek $B$ ye ulaşırız. O halde yine $l$ den geçen $A$ ile başlayan $B$ ile biten yönlere uyan bir yol vardır.
Aynı $p$ yolunda iki farklı $K_1$ ve $K_2$ ardışık olmayan köşelerin seçilemeyeceğini ispatlayalım. Diyelim böyle $K_1$ ve $K_2$ var. O zaman $K_1$ ile $K_2$ arasında kenar vardır. $p$ yolu $S_1S_2\dots S_vK_1L_1\dots L_tK_2R_1R_2\dots R_u$ olursa $S_1\dots S_vK_1K_2R_1\dots R_u$ daha kısa bir yol olup bu haritayı oluşturma biçimimizle çelişir; çünkü her adımda uç noktaları $m_i$ de olan geriye kalan köşeleri dışarıdan olan en kısa ekonomik yolu alıyorduk. Bu durumda $S_1\dots S_vK_1K_2R_1\dots R_u$ yu seçmiş olmamız ve dolayısıyla $K_1K_2$ yi kendimiz çizmiş olmamış gerekirdi ki $K_1$ ve $K_2$ $H$ de ardışık olmayan köşeler olup bu bir çelişkidir.
$AX$ kenarı veya $YB$ seçilirse $A\to X\to \dots \to B$ ve $A\to \dots \to Y\to B$ den dolayı $AX$ veya $YB=l$ olursa yine $l$ den geçen ve şartları sağlayan bir yol vardır.
$A$ ve $B$ dışındaki her nokta bir yolun içinde nokta olduğundan bütün prosedür doğru olup A kenti B kentine $\left(2n-3\right)-$yönlü bağlanabilir. Bu da soruyu bitirir.
