Feladat: N.112 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bérczi Gergely ,  Braun Gábor ,  Frenkel Péter ,  Juhász András ,  Kiss Tamás ,  Lippner Gábor ,  Mátrai Tamás ,  Pap Gyula ,  Szabó Jácint ,  Terék Zsolt ,  Terpai Tamás 
Füzet: 1997/április, 225 - 226. oldal  PDF file
Témakör(ök): Gráfelmélet, Szélsőérték-feladatok differenciálszámítás nélkül, Nehéz feladat
Hivatkozás(ok):Feladatok: 1996/október: N.112

Egy n3 szögpontú teljes gráf éleit úgy akarjuk k színnel kiszínezni, hogy egy él több színt is kaphat, de
(1) egyetlen szín se szerepeljen minden élen,
(2) egyetlen élen se szerepeljen minden szín, és
(3) bármely háromszögben minden színnel páratlan számú él legyen kiszínezve.
Mekkora k minimális értéke?

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.

Tekintsünk egy n csúcsú gráfot, amelyet a feltételeknek megfelelően kiszíneztünk k színnel. A gráf minden csúcsához hozzárendelünk egy k hosszúságú, nullákból és egyesekből álló sorozatot. Legyen a gráf egy csúcsa A. Ehhez rendeljük a csupa 0-ból álló sorozatot. Egy tetszőleges, A-tól különböző B csúcshoz rendelt sorozat i-edik eleme legyen 0, ha az AB élen szerepel az i-edik szín, és 1, ha nem szerepel.
Ha B és C két, A-tól és egymástól különböző csúcs, és a hozzájuk rendelt sorozatban az i-edik elem megegyezik, akkor az i-edik szín vagy az AB és AC éleken is szerepel, vagy egyiken sem; mivel az ABC háromszögben a (3) feltétel miatt páratlan sokszor kell szerepelnie, mindenképpen szerepelnie kell a BC élen. Ha pedig a B-hez és C-hez rendelt sorozatban az i-edik elemek különbözőek, akkor az i-edik szín az AB és AC élek közül pontosan az egyiken szerepel, tehát BC-n nem szerepel.
Összefoglalva, a (3) feltételből következik, hogy tetszőleges XY élen akkor és csak akkor szerepel az i-edik szín, ha a hozzájuk rendelt sorozatban az i-edik elem ugyanaz. Ennek a megfordítása is igaz: ha tetszőleges XY élen akkor és csak akkor szerepel az i-edik szín, ha a hozzájuk rendelt sorozatban az i-edik elem ugyanaz, akkor bármely háromszögben a csúcsokhoz rendelt sorozatok i-edik eleme vagy megegyezik (ebben az esetben mindhárom színen szerepel az i-edik szín), vagy pontosan két egyenlő van (és akkor a háromszögnek pontosan egy élén szerepel az i-edik szín).
A (2) feltétel azzal ekvivalens, hogy nem rendeltük két csúcshoz ugyanazt a számot.
Az (1) feltétel pedig azt jelenti, hogy nincs két olyan csúcs, amelyekhez rendelt sorozat egymás komplementere (azaz a 0-kat 1-esekre cseréljük és fordítva).
A feltételek tehát azzal ekvivalensek, hogy a

(0,0,0,...,0,0),(1,1,...,1,1);(0,0,0,...,0,1),(1,1,...,1,0);(0,0,0,...,1,0),(1,1,...,0,1);(0,1,1,...,1,1),(1,0,...,0,0);
sorozat-párok mindegyikéből legfeljebb egy szerepel a csúcsokon. Mivel a sorozatpárok száma 2k-1, ebből következik, hogy 2k-1n.
Megfordítva, ha 2k-1n, akkor kiválasztható a szükséges n darab (k hosszúságú) számsorozat, és azokból a megfelelő színezés. A színezhetőség szükséges és elégséges feltétele tehát, hogy 2k-1n, azaz klog2n+1 legyen.
 Kiss Tamás és Lippner Gábor (Fazekas M. Főv. Gyak. Gimn., III. o.t.)
 
  dolgozatai alapján