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?
Segítség, útmutatás: 3.14
Először színezzünk ki egy négy pontú teljes gráfot két színnel úgy, hogy ne legyen háromszínű háromszög, majd sokszorozzuk meg a pontjait.