Gráfelméleti feladatban tudnátok segíteni?

A Bergengóc Közlekedési Minisztérium felkért egy légitársaságot, hogy indítson ingajáratokat az ország legfontosabb városai között úgy, hogy egy városból legfeljebb három másikba induljon járat, de legfeljebb egy átszállással el lehessen jutni bármelyik városból bármelyik másikba. Legfeljebb hány város között lehet megszervezni ilyen összeköttetést? (Ingajárat: két város közti összeköttetés)

Már sikerült megalkotnom nyolcpontú gráffal (rajzoltam egy nyolcszöget az oldalaival és a négy szemközti csúcsot átlóval összekötöttem, így minden pontnak három lett a fokszáma és el is lehet jutni maximum 1 átszálással minden pontból minden másikba.

9 pontra viszont már nem akar kijönni a gráf, azt sejtem, hogy már nem is fog működni. Hogyan lehetne ezt bebizonyítani?

Addig jutottam, hogy 9 pont esetén a maximális fokszámösszeg 27 lehet.