Matematika gráfos feladat. Elmagyaráznád?

Nem hiszem, hogy úgy jön ki a 9.

A teljes gráfnak lehet 6·5/2 = 15 éle. (Ez ugye érthető, hogy miért?) Ebből minimum 12-őt kell kiválasztani:

Pont 12: 15 alatt a 12 = 455 féleképpen

Pont 13: 15 alatt a 13 = 105 féleképpen

Pont 14: 15 alatt a 14 = 15 féleképpen

Pont 15: 15 alatt a 15 = 1 féleképpen

Összesen 576 jön ki (nem pedig 676)

Ha nem számít, hogy melyik csúcs melyik... sajnos nem jövök rá, hogy hogyan lehet kiszámolni. Láthatólag 64-nel kell elosztani az 576-ot hogy 9 jöjjön ki, és 64 éppen 2^6, de nem tudom, miért pont így... Késő van már, úgy látszik.

Nem értek igazán a gráfelmélethez, úgyhogy nem vagyok benne egyáltalán biztos, hogy ez a legjobb megoldása a második résznek, de nem jut jobb eszembe:

15 élű gráfból egyetlen egy fajta lehet: a teljes gráf, minden csúcs 5 fokú. Fokszámsorozata:

(a) 5,5,5,5,5,5

14 élű: szintén 1 fajta:

(b) 5,5,5,5,4,4

úgy jött ki, hogy a teljes gráfból az egyik élet elhagytuk, ezért az él két végén lévő két 5 fokszámú csúcsból 4 fokszámúak lettek.

13 élű: elhagyhatunk két 5 fokszámú csúcs közötti élet: (két 5-ösből két 4-es lett)

(c) 5,5,4,4,4,4

vagy egy 5 és egy 4 fokszámú csúcs közöttit: (5,4-ből 4,3 lett, de átrendeztem csökkenő sorba a fokszámokat)

(d) 5,5,5,4,4,3

Több nincs, (b)-ben a két darab 4 fokszámú csúcs között nincs él, azt nem hagyhatjuk el.

12 élű: A (c) fokszámsorozatból (5,5,4,4,4,4) kiindulva egy újabb élet elhagyva ezek lehetnek:

(e) 4,4,4,4,4,4 (5,5 csúcsok közötti élet hagyunk el)

(f) 5,5,4,4,3,3 (4,4 közöttit dobunk el)

(g) 5,4,4,4,4,3 (5,4 közöttit dobunk el)

Vagy a (d)-ből (5,5,5,4,4,3) indulunk ki:

--- 5,4,4,4,4,3 (5,5 közöttit dobunk el, ugyanaz, mint g)

(h) 5,5,5,3,3,3 (4,4 közöttit dobunk el)

--- 5,5,4,4,3,3 (5,4 közöttit dobunk el, ugyanaz, mint f)

(i) 5,5,5,4,3,2 (4,3 közöttit dobunk el)

Ez összesen 9 féle lehetőség (a)-tól (i)-ig.

Biztos van szebb megoldás is...

Picivel érthetőbb megoldás a második részre:

A legalább 12 élű 6 csúcsú gráf komplementer gráfja legfeljebb 3 élű, hisz a teljes gráf 15 élű. Ebben a komplementer gráfban könnyebb megkeresni, hogy mely elrendezések lehetnek. Itt egy ábra hozzá:

[link]

Természetesen ezek száma ugyanaz, mint az eredeti gráfban a legfeljebb 12 élű gráfok száma.

-----

Ha meglesz az igazi megoldás, írd már meg, érdekel.