Élszínezés
2015-07-03 6:55
Pontok, vonalak, színesceruzák...
Közepes, beküldte:
bolnyi*, szerkesztő: csibe08
Van egy n szögpontú teljes gráfunk, amelynek minden élét pirosra vagy kékre 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ű.
Adjuk meg azt az n pozitív egész számot, melyre igaz az, hogy az n szögpontú gráf éleit bárhogy színezzük pirosra vagy kékre, mindenképpen tartalmazni fog egyszínű háromszöget, viszont ez az állítás (n-1) szögpontú gráf esetén még nem igaz.
