$n$ Köşeli Bağlantılı Çizgede İki Özellik

Question

$\color{red}{\textbf{Teorem:}}$ $n$ köşeli bağlantılı (ve basit) bir $G$ çizgesinde

$\color{blue}{\textbf{(a)}}$ kenar sayısı $\geq n$ ise en az bir döngü vardır,

$\color{blue}{\textbf{(b)}}$  $\displaystyle{\sum_{v\in G}\deg(v) \geq 2(n-1)}$ dir, ispatlayınız.

Answer 1

$n$ köşeli bir bağlantılı basit çizgede döngü yoksa bir ağaç olur ve dolayısıyla kenar sayısı $n-1$ olur.
Bu da kenar sayısının $\ge n$ olması ile çelişir.

Her kenar iki köşeye sahip olduğundan derece toplamı kenarlar sayısının iki katına eşit olur.
Tümevarım ile $n$ köşeli bir bağlantılı basit çizgede en az $n-1$ kenar olması gerektiği gösterilebilir.

Answer 2

$(a)$ kısmı için aynı çözüm yoluna sahibim.

$(b)$ için bakalım: $n\geq 1$ köşeli bir ağaç çizgede $n-1$ kenar olması gerektiğini biliyoruz. $n$ köşeli bağlantılı (ve basit) bir $G$ çizgesinde kenar sayısının $n-1$ den az olamayacağını ispatlayalım.

Eğer $G$ döngü içermiyorsa bir ağaç olur ve kenar sayısı tam olarak $n-1$ dir.

Şimdi, $G$ döngü içeriyor olsun. Bu durumda $G$ nin kenar sayısı $e$ için $e< n-1$ olabilir mi? İnceleyelim. $G$ nin döngü oluşturmasını engelleyecek şekilde bazı yolları silmeye başlayalım. $(v_0, v_1, v_2, \dots, v_k)$ yolunu sildiğimiz zaman $v_0$ başlangıç köşesini ve $v_k$ bitiş köşesini silmiyoruz. Arada kalan kenarları siliyoruz. $k-1$ tane kenarı silmiş oluyoruz. Aradaki $k-1$ tane köşenin de tamamını veya bazılarını silmiş oluyoruz. Çünkü bir $v_i$ köşesi başka bir kenarın da uç noktası olabilir. Yani $(v_0, v_1, v_2, \dots, v_k)$ yolu üzerinden en çok $k-1$ tane köşe silmiş oluyoruz. Bu şekilde silme işlemleri yaparak, $G$ çizgesinden bir ağaç elde ederiz. $t$ tane kenar ve $t$ tane köşe silindiği zaman bu ağaçta $e-t$ tane kenar ve en çok $n-t$ tane köşe kalır.

$$\text{Ağaç Çizgenin Köşe Sayısı} \leq n - t < e - t - 1 \tag{1}$$

$$\text{Ağaç Çizgenin Köşe Sayısı} = \text{Ağaç Çizgenin Kenar Sayısı} -1 = e - t - 1 \tag{2}$$

eşitsizliklerinden çelişki elde edilir. Yani bağlantılı bir $G$ çizgesinde $e< n-1$ olamaz. O halde $e\geq n-1$ dir. El sıkışma teoremi gereğince $$\displaystyle{\sum_{v\in G}}\deg(v) = 2e \geq 2(n-1)$$ sonucuna ulaşırız.

Eşitlik durumu ancak ve ancak $G$ bağlantılı çizgesi bir ağaç iken sağlanır. Çünkü $n-1$ kenarlı bağlantılı $G$ çizgesinde döngü varsa, yine döngü oluşmasına neden olan yolları silerek çizgeyi bir ağaca indirgeyip bir çelişki bulabiliriz.

 

$\color{red}{\text{Dikkate Değer Bazı Sonuçlar:}}$

$\color{red}\bullet$ $G$ ağaç çizgesindeki bağlantısız olan herhangi iki $v_1$, $v_2$ köşesini birleştirirsek mutlaka bir döngü oluşur.

$\color{red}\bullet$ $G$ ağaç çizgesindeki bağlantı olan herhangi iki komşu $v_1$, $v_2$ köşesinin arasındaki $e$ kenarını kaldırırsak oluşan $G-e$ çizgesi bağlantısız olur.