Élszínezés 2.
2015-08-26 6:55
Továbbra is rajzolgatunk, színezgetünk, számolgatunk...
Nehéz, beküldte:
bolnyi*, szerkesztő: csibe08
Van egy 17 szögpontú teljes gráfunk, amelynek minden élét pirosra, kékre, vagy sárgára színezzük. Teljes gráf alatt az összes lehetséges él berajzolását értjük. Vezessük be a következő definíciót: a gráf akkor tartalmaz egyszínű háromszöget, ha van három olyan pontja, amelyek között futó mindhárom él azonos színű.
Először bizonyítsuk be, hogy ebben a gráfban - tetszőleges színezés mellett - mindenképpen lesz egyszínű háromszög! (5 pont)
Aztán színezzük ki egy 16 szögpontú gráf éleit három színnel úgy, hogy legfeljebb 8 db egyszínű háromszöget tartalmazzon! (5 pont)
