Feladat: 3.4.
Bizonyítsuk be, hogy ha egy hatpontú teljes gráf éleit két színnel színezzük, akkor van legalább két egyszínű háromszög. Van-e mindig három egyszínű háromszög is?
 

Megoldás: 3.4
Egy egyszínű háromszög van a 3.3. feladat szerint. Hagyjuk el e háromszög egyik x pontját. A maradó ötpontú gráfban vagy van még egy egyszínű háromszög, vagy úgy van két színnel színezve, hogy mindkét színű élek egy C5 -öt alkotnak. (L. a 3.2. feladatot.) Előbbi esetben kész vagyunk. Utóbbi esetben x-et az öt pont közül legalább hárommal azonos színű él köti össze, legyen ez az 1-es szín. Az 1-es színű C5 szerint számozzuk a pontokat mod 5, tehát az 123451 kör élei 1-es színűek. Minthogy három 1-es színű él indul x-ből, ezek közül kettő a kör szomszédos pontjaihoz indul. Úgy számozunk, hogy x össze van kötve 1-gyel és 2-vel. Ha 3-mal vagy 5-tel is 1-es színű él köti össze, akkor x12 mellett van még egy 1-es színű háromszögünk, ha viszont 3-mal is, 5-tel is 2-es színű él köti össze, akkor x35 egy 2-es színű háromszög. A ,,három-ház-három-kút" ( K3,3 ) gráfban nincs háromszög (mert páros gráf) és a kompelemtere két diszjunk háromszög. Legyenek a két diszjunkt háromszög élei 1-es színűek, a többi él 2-es színű. E mellett a színezés mellett nincs három egyszínű háromszög.