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

'''Tétel''': Minden <math>k\geq 2</math> egész számra létezik olyan <math>G_k</math> gráf, melyre <math>\omega(G_k)=2</math> és <math>\chi(G_k)=k</math>. Ez azt jelenti, hogy a [[Kromatikus szám|kromatikus szám]] felső korlátja nem függ a klikkszámtól.

 

 

[[Teljes indukció]]val belátjuk, hogy <math>G_k</math> egyetlen <math>k</math>-ra sem tartalmaz háromszöget, azaz a klikkszáma 2. <math>k=2</math>-re igaz az állítás, hiszen <math>G_2</math> a 2 pontú [[teljes gráf]]. Tegyük fel, hogy <math>G_k</math>-ban nincs háromszög. [[Indirekt bizonyítás]]sal belátjuk, hogy <math>G_{k+1}</math>-ben sincs. Tegyük fel, hogy mégis van <math>G_{k+1}</math>-ben háromszög. Ennek a háromszögnek legalább az egyik csúcsa nincs <math>G_k</math>-ban, mert <math>G_k</math> az indukciós feltevés szerint nem tartalmaz háromszöget. Ha a háromszög tartalmazza a <math>w</math>-vel jelölt csúcsot, akkor a másik két csúcs csak <math>u</math>-val jelölt lehet, azok azonban nincsenek összekötve. Már csak az az eset maradt, hogy a háromszög tartalmaz egy <math>u</math>-val jelölt csúcsot (<math>u_i</math>). Ekkor a másik két csúcs csak <math>v_x</math> és <math>v_y</math> lehet. <math>u_i</math> pontosan azokkal a csúcsokkal van összekötve, amelyekkel <math>v_i</math>, vagyis <math>v_i</math>, <math>v_x</math> és <math>v_y</math> is háromszöget alkot <math>G_k</math>-ban, ez pedig ellentmond az indukciós feltevésnek.

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 <math>k>3</math> 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 <math>k\geq 3</math> 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 <math>k\geq 4</math> 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.

 

 

==[[Hamilton-kör]] a Mycielski-gráfban==