Adott öt város úgy, hogy közülük bármely 3-ból kiválasztunk kettőt, amelyeket út köt össze. Bizonyítsd be, hogy az utak száma legalább négy?

Gráfelméleti megközelítés: öt csúcs adott, és minden kiválasztott 3 csúcs között van legalább egy él.

Tegyük fel, hogy maximum 3 éle van a gráfnak. Ekkor az élek legyenek e1, e2, e3.

Nézzük meg azt az esetet, amikor ezek között csak egy független él van, azaz mindhárom él érint egy csúcsot. Ekkor van egy csúcs, aminek 3 a foka, van három csúcs, aminek 1 a foka és egy aminek 0. Ha kiválasztunk kettőt amelynek egy a foka és a 0 fokút, akkor a kiválasztott három pont között nem lesz egyetlen egy él sem. -> Legalább 4 éle van a gráfnak.

A másik eset, amikor legalább két él független, azaz van egy e1 és e2 él, amelyek négy különböző csúcsot tartalmaznak. Legyen A->B és C->D csúcs az ötödik csúcs pedig E. Az ACE, ADE, BCE, BDE csúcshármasokban nincs benne az AB és CD él sem, ezért egyikben sincs él. A harmadik élet nem lehet úgy megválasztani, hogy mind a négy csoportba legalább egy él kerüljön. -> Legalább négy éle van a gráfnak.

Kicsit hosszúra sikerült, de impróztam. sry.