Matematické Fórum

Ahoj,
zas jsem narazil na úlohu, se kterou si AI neví rady, přitom snad není tak těžká.

Nechť Kn je úplný graf na n vrcholech (v celé úloze uvažujeme jen úplné grafy), každá jeho hrana je obarvena jednou z n-1 barev tak, že z žádného vrcholu nevychází dvě hrany stejné barvy. Dále platí, že hrany každého podgrafu K4 jsou obarveny právě 3 nebo právě 6 barvami. A chceme dokázat, že v každém podgrafu K3 dvě barvy jednoznačně určují třetí barvu, přesněji: Nechť máme podgraf K3 s hranami obarvenými barvami a,b,c a nechť máme další podgraf K3, jehož dvě hrany mají barvy a,b - tak potom už musí mít třetí hrana také barvu c.