Feladat:	N.119	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bérczi Gergely ,  Braun Gábor ,  Frenkel Péter ,  Gyenes Zoltán ,  Hesz Zoltán ,  Juhász András ,  Kun Gábor ,  Lippner Gábor ,  Mátrai Tamás ,  Pap Gyula ,  Szabó Jácint ,  Vizer Máté
Füzet:	1997/április, 230 - 231. oldal		PDF  |  MathML
Témakör(ök):	Gráfelmélet, Indirekt bizonyítási mód, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1996/november: N.119

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Minden $k$ pozitív egészre konstruálunk olyan $G_k$ háromszögmentes gráfot, amely nem színezhető ki $k$ színnel. Ha $k=1$, akkor a két pontú, egy élű gráf megfelelő. Tegyük fel, hogy már megkonstruáltuk $G_{k-1}$-et; most megkonstruáljuk $G_k$-t. Legyen $G_{k-1}$ pontjainak száma $s$, és legyen $N$ pozitív egész ($N$ pontos értékét később határozzuk meg), vegyünk fel egy $N$-elemű $H$ ponthalmazt, valamint $\left(\genfrac{}{}{0ex}{}{N}{s}\right)$ darab, $G_{k-1}$-gyel izomorf gráfot, legyenek ezek $G_{k-1}^1$, $\text{...}$, $G_{k-1}^{\left(\genfrac{}{}{0ex}{}{N}{s}\right)}$. Mindegyik $G_{k-1}^i$-nek feleltessük meg $H$ egy $s$-elemű részhalmazát, és kössük össze $G_{k-1}^i$ minden pontját a megfelelő részhalmaz egy-egy pontjával. Azt állítjuk, hogy az így kapott gráf háromszögmentes, és megfelelő $N$ esetén nem színezhető ki $k$ színnel. Ha lenne háromszög, akkor annak legfeljebb egy csúcsa lehet $H$-ban, mert $H$-beli pontok között nincs él. Nem lehetnek csúcsai különböző $G_{k-1}^i$-kben sem, mert az ilyenek között sincs él. Nem lehet mindhárom pont ugyanabban a $G_{k-1}^i$-ben sem, mert $G_{k-1}^i$ háromszögmentes. Már csak az az eset maradt, hogy egy csúcsa $H$-ban van, a másik kettő pedig ugyanabban a $G_{k-1}^i$-ben. Viszont $H$-beli pontból legfeljebb egy $G_{k-1}^i$-beli pontba megy él. Tegyük fel, hogy a gráfot kiszíneztük $k-1$ színnel. Ha $N$ elég nagy, például $N>\left(s-1\right)\left(k-1\right)$, akkor $H$-ban van $s$ darab egyszínű pont, legyen ezek színe piros. Az ezeknek megfelelő $G_{k-1}^i$-ben nem szerepelhet a piros szín, ez viszont ellentmond annak, hogy legalább $k-1$ szín szükséges a színezéséhez.  Több dolgozat alapján    II. megoldás. Egy másik konstrukciót mutatunk. Tegyük ismét fel, hogy $G_{k-1}$ már létezik, pontjai legyenek $P_1$, $\text{...}$, $P_s$. Vegyük még fel a $Q_1$, $\text{...}$, $Q_s$ és $R$ pontokat. Kössük össze $P_i$-t $Q_j$-vel, ha $P_i$ és $P_j$ össze van kötve, továbbá kössük össze $R$-et mindegyik $Q_i$-vel. Ha az így kapott gráfban lenne háromszög, annak legfeljebb egy csúcsa lehet a $Q_i$-k között, mert a $Q_i$-k között nem fut él; ebből kifolyólag $R$ sem szerepel háromszögben. Ha pedig $P_i$, $P_j$ és $Q_l$ háromszöget alkot, akkor $P_i$, $P_j$ és $P_l$ is, ami ellentmond annak, hogy $G_{k-1}$ háromszögmentes. Tegyük fel, hogy a gráf kiszínezhető $k-1$ színnel. Legyen $R$ színe piros. Megadjuk a $P_1$, $\text{...}$, $P_s$ pontok egy jó színezését $k-2$ színnel. Ez ellent fog mondani annak, hogy $G_{k-1}$ színezéséhez legalább $k-1$ szín kell. Minden egyes piros $P_i$-t változtassuk $Q_i$ színére. A $Q_i$ pontok között nem szerepel a piros szín, mert közös szomszédjuk, $R$ piros. A $P_i$-ket tehát csak legfeljebb $k-2$ színnel színeztük. Ha $P_i$ és $P_j$ között fut él, akkor vagy mindkettő színét változatlanul hagytuk, és emiatt különbözőek maradtak, vagy az egyikük piros volt (mondjuk $P_i$), és annak színét $Q_i$ színére változtattuk. Viszont $Q_i$ és $P_j$ között van él, $Q_i$ és $P_j$ színe különböző volt, tehát a módosított színezésben is $P_i$ és $P_j$ különböző színű.  Több dolgozat alapján