Legkevesebb hány bolygó között kell létrehozni a járatokat, ha az iroda a 4 legkisebb bolygó közül semelyik kettő között nem indít közvetlen űrjáratot?

Nem tudom, jól értem-e a feladatot, de nekem ez jött le belőle:

A gráfban a bolygók a csúcsok, a járatok az élek, a bolygóról induló járatok száma a csúcs fokszáma.

Elvileg lehet 1, 1+2(=3), 1+2+3(=6), 1+2+3+4(=10), 1+2+3+4+5(=15), 1+2+3+4+5+6(=21), 1+2+3+4+5+6+7(=28), stb bolygó, hogy a járatszám feltételnek esélye legyen teljesülni.

Ekkor a fokszámok összege:

1: 1

3: 1+2·2 = 5

6: 1+2·2+3·3 = 14

10: 1+2·2+3·3+4·4 = 30

15: 1+2·2+3·3+4·4+5·5 = 55

21: 1+2·2+3·3+4·4+5·5+6·6 = 91

28: 1+2·2+3·3+4·4+5·5+6·6+7·7 = 140

stb.

Páratlan fokszám nem lehet, mert egy él 2 fokszámot generál a két végével, tehát páros kell legyen az összeg. Vagyis talán lehet 6, 10, 28, stb. darab bolygó (és 14, 30, 140, stb. fokszámösszeg, vagyis 7, 15, 70 stb. él)

A másik feltétel, hogy a 4 legkisebb bolygó között nincs járat. 6 bolygó esetén ez nem megy, mert a 4 kis bolygó csak a maradék 2 másikhoz kapcsolódhatna, vagyis a 2 űrjáratos bolygóból túl sok lenne.

10 bolygó viszont lehet, pl. így:

A 4 kis bolygót nevezzük a,b,c,d-nek, a maradék 6 nagyot pedig A,B,C,D,E,F-nek. Rajzold fel a felső sorba a 4 kicsit, alá a 6 nagyot. Ilyen élek lesznek:

aA, aB, aC

bA, bB, bC

cA, aB, cC

dC, dD, dE, dF

AB

DE

Vagyis a bolygók fokszáma:

1: F

2: D, E

3: a, b, c

4: d, A, B, C

Biztos lehet másmilyen összekapcsolás is, de legalább 10 bolygó kell.