Matematické Fórum

Ahoj,

potřeboval bych dokázat, že Petersenův graf není 1-faktorizovatelný (tj. jeho hrany nelze vzít a rozebrat je na několik perfektních párování). Je mi jasné, že tenhle graf má 1-faktor/perfektní párování (tj. zde to bude graf se všemi původní vrcholy + pouze s hranami spojujícími vnitřní a vnější pěticyklus). Dále jsem si ověřil, že po vybrání všech hran tohoto 1-faktoru z původního grafu mi zůstane 2-faktor - "vnější" a "vnitřní" pěticyklus.

Jenže to je ale asi všechno. Napadá mne: a) vybrat všechny možné 1-faktory navzájem neizomorfní a ukázat pro každý zvlášť, že zbytek není 1-faktor a ani ho v sobě nemá (to je ale nepříliš hezký přístup); b) kdesi jsem vygooglil, že 1-faktorizovatelnost k-regulárního grafu odpovídá možnosti obarvit hrany grafu k barvami. Petersenův graf je 3-regulární (tj. má všechny vrcholy stupně 3), jenže dle Brooksovy věty jej lze obarvit nejméně 4-mi barvami. Avšak vůbec jsem nepochopil důkaz toho předpokladu 1-faktorizovatelnosti.

Nemáte někdo nějaký nápad, popř. radu, na jakou vlastnost grafu bych se měl zaměřit?

Předem díky za odpověď.

V.