Feladat: 3.14.
Egy
m csúcsú teljes gráf éleit akarjuk három színnel színezni úgy, hogy mind a három szín valóban elő is forduljon, de ne legyen ,,tarka" háromszög, azaz olyan háromszög, amelynek mind a három éle különböző.
Lehetséges-e ez?
Megoldás: 3.14
Igen. Osszuk a gráf csúcsait négy osztályba, legyenek ezek
A,
B,
C és
D. Az
AA,
BB,
CC és
DD éleket színezzük pirosra, az
AB és
CD éleket színezzük kékre, a többit, tehát az
AD,
BC,
BD és
AC éleket színezzük zöldre. Ez a színezés megfelel.