Matematické Fórum

Dobrý den,
uvést všechny grafy (až na izo) splňující nějaké podmínky mi občas připadne docela těžké, na nic nezapomenout, nic nevynechat, o to bych se zde rád pokusil.
Těch zadání je víc, sem dám ten první, samozřejmě. Díky za pomoc a případné doplnění.

Nechť d je celé číslo větší nebo rovno 1.
Najděte všechny vzájemně neizomorfní d-regulární grafy, které mají deset vrcholů
a splňují .

d-regulární ... každý vrchol má stupeň d
chi(G)>d ... (vrcholové) chromatické číslo je větší než d

Použiju větu
Je-li G souvislý graf, pak chromatické číslo chi(G) se rovná maximálnímu stupni vrcholu +1 právě tehdy, když
G je graf úplný nebo cyklus délky 7.
(max stupeň v grafu jsme značili delta(G), takže bych si dovolil )

Takže chci uvést grafy, kde nějaké komponenty jsou úplné, musí to být regulární, nebo cykly liché délky.
To vše na deseti vrcholech.
1) úplný graf K10 (je 9 regulární a potřebujeme 10 barev)
2) dvě komponenty: K5, K5 (jsou 4 regulární a potřebujeme 5 barev)
3) pět dvojic vrcholů, které jsou spojeny hranou (1-reg, 2 barvy)
4) K_3,3 úplný bipartitní graf a K4 (je to na deseti vrcholech, 3 regulární, 4 barvy potřeba kvůli komponentě K4)
5) K4 a 3-regulární graf na 6 vrcholech (je takový jen jeden?)
6) C7 a C3 (2-reg, 3 barvy)
7) C5, C5
8) C3, C3, C4

víc jich nemám, ale myslím, že devátý by měl existovat...možná v té 5) se skrývají dva. Nevím.
Díky za pomoc.
kolejo