Egy országban minden városból legfeljebb 3 másik városba közlekedik repülőjárat. Tudjuk, hogy bármelyik városból bármelyik másikba el lehet jutni legfeljebb 1 átszállással. Legfeljebb hány város lehet az országban?

[link]

Szerintem 9.

A-ból el lehet jutni B, C, D-be közvetlenül és mindegyikből induljon ki még egy él E, F, G-be. Szerintem az EF, FG, EG élek mindegyikének léteznie kell. Tehát egy háromszöget rajzoljál (EFG), bele egy pontot (A), és tegyél 1-1-1 pontot az E-A,F-A,G-A szakaszokra.

Ha úgy gondolkozunk hogy nézzünk egy maximális élcsúcsú sokszöget akkor az ötszög lesz. Hozzáadhatunk még két pontot amik egymással össze vannak kötve és az ötszög két-két pontjához csatlakoznak. Ez is pont hét.

Tovább gondolkozva, az ötszöges nem jó, de az első példa igen.

De azt hiszem van egy nyolc pontos verzióm?? Induljunk ki megint AB, AC, AD élekből, képzeljünk három szintet, ahol az A az első, B,C,D a második, és legyen E,F,G,H a harmadik szinten. Húzzuk be a BE, BF, CG, CH, DG, DH éleket szintek között majd az EF, EG, FH éleket.

A-ból láthatóan el lehet mindenhova szintek közötti lépéssel.

B-ből A-ba közvetlen, C és D A-n keresztül, E, F közvetlen, G és H E ill F keresztül.

C-ből A közvetlen, B és C A-n keresztül, G és H közvetlen, E és F rajtuk keresztül. D nem különbözik C-től.

Hopp, megvan! [link] "It is the largest cubic graph with diameter 2"

[link]