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

Mycielski-gráfoknak azokat a gráfokat nevezzük, amelyek a két csúcsú [[Teljes_gráf|teljes gráfból]], vagyis a két pontból és egyetlen élből álló gráfból előállíthatóak a fenti eljárás egymás után következő véges számú alkalmazásával.

'''Tétel''': Minden k<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óvalindukció]]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ássalbizonyí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.

Teljes indukcióval látjuk be, hogy <math>\chi(G_k)=k</math>. <math>k=2</math>-re az állítás egyértelmű. Tegyük fel, hogy az állítás igaz <math>k</math>-ra. Indirekt belátjuk, hogy ekkor <math>\chi(G_{k+1})=k+1</math>. <math>G_{k+1}</math> színezhető jól <math>k+1</math> színnel a következő módon: Kiszínezzük a <math>G_k</math>-beli <math>v_i</math> csúcsokat <math>k</math> színnel jól (az indukciós feltevés miatt ez lehetséges), majd minden <math>u_i</math>-t <math>v_i</math> színére és <math>w</math>-t pedig a <math>(k+1)</math>-edik színnel. Azt kell tehát belátni, hogy erre a <math>k+1</math> színre szükség is van. Mivel <math>G_{k+1}</math> részgráfként tartalmazza a <math>k</math>-kromatikus <math>G_k</math> gráfot, <math>\chi(G_{k+1})</math> nem lehet kisebb <math>k</math>-nál. Tegyük fel indirekt, hogy <math>\chi(G_{k+1})=k</math>.

A színeket 1,2,...,<math>k</math>-val, <math>x</math> csúcs színét <math>c(x)</math>-szel jelöljük. Feltehetjük, hogy <math>c(w)=k</math>. Mivel minden <math>u_i</math> szomszédos <math>w</math>-vel, minden <math>u_i</math> csúcs színe az 1,2,...,<math>k-1</math> színek valamelyike lehet. Tekintsük a <math>v_i</math> csúcsok által feszített részgráfot, ez <math>G_k</math>-val izomorf. Most megadjuk a <math>v_i</math> csúcsok egy új, <math>c'</math> színezését, mely csak az 1,2,...,<math>k-1</math> színeket tartalmazza. <math>c(v_i)=k</math> esetén legyen <math>c'(v_i)=c(u_i)</math>, minden más esetben <math>c'(v_i)=c(v_i)</math>. Azoknál az éleknél, melyek végpontjainak színét nem változtattuk meg, nem lehet probléma. Azon <math>v_i</math> csúcsoknak, melyekre <math>c(v_i)=k</math> teljesül, nincs olyan <math>v_j</math> szomszédja, melyre <math>c(v_j)=k</math>, mert <math>c</math> egy jó színezés volt. Ekkor <math>c'(v_j)=c(v_j)</math> <math>v_i</math> minden <math>v_j</math> szomszédjára teljesül. Gond csak akkor lehet, ha <math>c(u_i)=c'(v_i)=c'(v_j)=c(v_j)</math>. <math>c(u_i)=c(v_j)</math> azonban nem teljesül, mert ha <math>v_i</math> és <math>v_j</math> szomszédosak, akkor <math>u_i</math> és <math>v_j</math> is, <math>c</math> pedig jó színezés. Tehát a <math>v_i</math> csúcsok színezhetőek jól úgy, hogy csak az 1,2,...,<math>k-1</math> színeket használjuk. Ez viszont ellentmond annak, hogy a <math>v_i</math> csúcsok <math>G_k</math>-val izomorf feszített részgráfja k-kromatikus. Emiatt <math>\chi(G_{k+1})>k</math>. Ebből és <math>\chi(G_{k+1})<=k+1</math>-ből az következik, hogy <math>\chi(G_{k+1})=k+1</math>.

A ''<math>k''</math>-kromatikus <math>M_k</math> Mycielski-konstrukcióval kapott gráf csak ''<math>k''=3</math>-ra tartalmaz Euler-kört.

<math>M_1</math> egy pontból, <math>M_2</math> két pontból és egy élből áll, tehát nem tartalmaznak Euler-kört. <math>M_3</math> egy 5 pontból álló kör, amiben van Euler-kör. A konstrukcióból adódik, hogy ugyanannyi <math>v</math> típusú csúcs van, mint amennyi <math>u</math> típusú, tehát ''<math>k''&ge;\geq 3</math> esetén <math>w</math>-vel együtt páratlan sok csúcs van. <math>M_{k+1}</math>-ben a <math>w</math> csúcsnak <math>|V(M_k)|</math> szomszédja van, ami ''<math>k''&ge;\geq 3</math> esetén páratlan, így ''<math>w''</math> páratlan fokú. Tehát ''<math>k''>3</math>-ra a Mycielski-gráf nem tartalmaz Euler-kört.

Az <math>M_k</math> Mycielski-gráf csak <math>k=2</math> és <math>k=3</math> 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 <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 k<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 k<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.

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ú, <math>k>3</math> esetén pedig 2-nél több ilyen pár van a gráfban.