„Mycielski-konstrukció” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Hibák javítása |
hibák javítása |
||
26. sor:
==[[Euler-kör|Euler-út]] a Mycielski-gráfban==
Az <math>M_k</math> Mycielski-gráf csak k=2 és k=3 esetén tartalmaz Euler-utat.
Könnyen ellenőrizhető, hogy <math>M_2</math> és <math>M_3</math> tartalmaz Euler-utat. A következőkben azt látjuk be, hogy a Mycielski-gráfnak k>3 esetén 2-nél több páratlan fokú csúcsa van, ezért nem tartalmaz Euler-utat. Ha <math>M_k</math>-ban <math>v_i</math> fokszáma <math>d</math>, akkor <math>M_{k+1}</math>-ben <math>u_i</math> fokszáma <math>d+1</math>, hiszen össze van kötve <math>v_i</math> <math>M_k</math>-beli szomszédaival és <math>w</math>-vel, de más csúccsal nem. <math>v_i</math> <math>M_{k+1}</math>-ben össze van kötve az <math>M_k</math>-beli szomszédaival, illetve azok <math>u</math> jelű párjaival, vagyis <math>2d</math> szomszédja van <math>M_{k+1}</math>-ben. Ebből következik, hogy k>=3 esetén, a Mycielski-gráf <math>v</math>-vel jelölt csúcsai páros fokúak, míg az <math>u</math>-val jelölt csúcsai páratlan fokúak, hiszen k>=4 esetén minden <math>u</math> csúcs foka 1-gyel nagyobb, mint a párjáé. Ekkor az <math>u_i</math>-k száma mindig nagyobb kettőnél.
Megjegyzés: A probléma úgy is megközelíthető, hogy a konstrukcióból adódóan minden <math>v_i</math> és <math>u_i</math> párnál a fokszám 1-gyel tér el, tehát <math>v_i</math> és <math>u_i</math> különböző paritású, k>3 esetén pedig 2-nél több ilyen pár van a gráfban.
| |||