Segítene nekem valaki? Egy országban 9 nagyváros van. Ezek közül mindegyikből pontosan 4 nagyvárosba van oda és vissza is repülőjárat. Bizonyítsa be, hogy bármely nagyvárosból legfeljebb egy átszállással bármely nagyvárosba el lehet jutni!

Segítség: válassz ki tetszőlegesen két várost, két eset lehet:

- van közvetlen járat köztük, akkor jó

- nincs közvetlen járat, akkor könnyű bebizonyítani, hogy lesz olyan város, amelyik mindkettővel össze van kötve.

Ha a másodikat nem látod, hogy miért, akkor kezd el rajzolgatni gráfban a két össze nem kötött városnak a szomszédait, és rá fogsz jönni, miért is igaz.

Két része van a problémának: az első, hogy be kell bizonyítani, hogy a gráf összefüggő. Ez nagyon könnyű: legalább 5 pont kell ahhoz, hogy 4 fokú legyen minden pontja, tehát legalább 10 város kéne, ami nincs, tehát a gráf összefüggő.

A maradékot meg azt hiszem már elmondták.

Utazz busszal!:D

Csak vicc volt, de nem bírtam kihagyni.