Igazoljuk, hogy minden 8-reguláris gráfnak van 4-reguláris és 2-reguláris feszítőrészgráfja is. Egy 2-reguláris gráfnak van-e mindig olyan 1-reguláris feszítő részgráfja?

Tanultátok Petersen tételét, ugye? Keresd meg a jegyzetben. Azt mondja, hogy minden 2k-reguláris gráf felbomlik k darab éldiszjunkt 2-reguláris feszítőrészgráfra. Innen látod, mire megy ki a feladat?

1-reguláris nem mindig van, pl a páratlan köröknek nincs.

Ha K nem Hamilton-kör, akkor van olyan c csúcs, amin K nem pont egyszer megy át (kezdő- és végpontnál vigyázz, ott a felsorolásban kétszer szerepel a pont, pedig csak egyszer érinti a kör). Ha egy csúcson többször is átmegy, akkor bármely élét elhagyva a maradékban még mindig lesz kör, tehát nem utat kapunk. Ha egy csúcson egyszer se megy át: Mivel a gráf összefüggő, ebbe a c csúcsba vezet út K-nak egy p pontjából. Ha egy p-ből induló élet hagysz ki K-ból, akkor a maradék nem lesz maximális, hiszen folytathatod a p-ből c-be vezető úttal.