„Mycielski-konstrukció” változatai közötti eltérés

A '''Mycielski-konstrukció''' a <math>V(G)=\{v_1,...,v_n\}</math> csúcshalmazcsúcshalmazú <math>G</math> [[gráf]]hoz egy olyan <math>M(G)</math>-vel jelölt gráfot rendel, melyben feszített részgráfként szerepel a <math>G</math> gráf, továbbá még n+1 csúcs. Ezek a következő elrendezésben: Minden <math>G</math>-beli <math>v_i</math> csúcsnak van egy <math>u_i</math> párja, melynek szomszédsága megegyezik a <math>v_i</math> szomszédságával, vagyis azokkal és csak azokkal a csúcsokkal van összekötve, amelyekkel <math>v_i</math>. Az (n+1)-edik új csúcs (<math>w</math>) mindegyik <math>u_i</math> csúccsal össze van kötve, de egyetlen <math>v_i</math>-vel sincs.

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áé k>=4 esetén. Ekkor az <math>u_i</math>-k száma mindig nagyobb kettőnél.