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

0 beğenilme 0 beğenilmeme
36 kez görüntülendi

$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.

19, Mayıs, 2016 Lisans Matematik kategorisinde Sercan (23,831 puan) tarafından  soruldu

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.

1 cevap

0 beğenilme 0 beğenilmeme

$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.

20, Mayıs, 2016 Sercan (23,831 puan) tarafından  cevaplandı
...