$4$ten büyük her çift mertebe için $3$-düzenli çizgenin varlığı

Question

$n \ge 4$ çift bir tam sayı olsun. Mertebesi $n$ olan $3$-düzenli bir çizgenin mevcut olması gerektiğini gösteriniz.

Örneğin: $K_4$ bu şartlarda bir çizge. Bu nedenle $n=4$ için böyle bir çizge mevcut.

Comments

Hocam çok cahilce soruyorsam affet ama mertebesi tek olan 3- düzenli çizge var mıdır?

---

Kose sayisi $n$ olsa, dereceler toplami $3n$  olur. Dereceler toplami cift olmali, "el sıkışma", bu nedenle $n$ kesinlikle cift olmali.

---

ooo pardon sorunun başında çift yazıyormuş zaten,özür dilerim.

Answer 1

Şöyle bir çizim yaptım: $n=4, 6, 8, 10$ durumlarını görüyoruz.

Önce kareleri yan yana ekleyerek şeklimizi donatıyoruz. Sonra her bir kare için sol alt köşeden sağ üst köşeye uzanan köşegeni çizerek donatıyoruz.. Son hamlede de, oluşan dikdörtgende kesikli çizgilerle gönünen köşegeni çiziyoruz. Yani sağ alttan sol üste doğru donatıyoruz. (Cinci Abla'nın graf teorisi anlattığını hayal edelim.)  

 

$\color{blue}{\text{Not:}}$ Bu çizim, Sercan hocamın açıkladığı yönteme eşdeğer olmalıdır.

Answer 2

$n=4$ icin $K_4$ cizgesi $3$-duzenli.

$k \ge 4$ icin mevcut oldugunu var sayalim ve $k+2$ icin olasi gerektigini gosterelim:

$k$ icin var olan cizgenin koseleri $$v_1,\cdots, v_k$$ olsun ve buna su sekilde $$a,b$$ koselrini ekleyelim: cizgenin ilk halinden $$y$$  kosesi alalim ve buna komsu iki $$x,z$$ kose secelim. ($3$-duzenli oldugundan boyle $2$ kose var, hatta $3$ kose). Aradaki bu kenarlari silelim. (Eger basit cizge degilse aradaki kenarlardan birini secip silelim). Bu durumda dereceler $$d(x)=2,d(y)=1, d(z)=2$$ olur ve ilk cizgenin diger koselerinin derecesi $3$ olur. $a$ ile $b,x,y$ ve $b$ ile (ilk basta cizdigimiz $a$ ile arasindaki kose disinda) $y,z$ arasinda birer kose secelim. Bu koseler diger koselerin derecesini etkilemediginden $a,b,x,y,z$ disindaki koselerin derecesi $3$ olarak kalmaya devam eder ve $a,b,c,x,y$'nin dereceleri de $3$ tamamlanmis olur. Kisacasi mertebesi $k+2$ olan $3$-duzenli bir cizge elde etmis olduk.

Tumevarim ile ispat biter.