Mam problem z takim zadaniem:
Jeżeli spójność krawędziowa grafu G jest \(\displaystyle{ \ge 2}\) i graf jest 3-regularny, to G ma 1-faktor.
Chcę tylko powiedzieć, że to nie musi być prawda. Niestety ni umiem znaleźć kontrprzykładu ani wymyślić dowodu. Proszę o jakieś wskazówki
Faktory i spójność krawędziowa
-
- Użytkownik
- Posty: 231
- Rejestracja: 13 gru 2009, o 01:27
- Płeć: Mężczyzna
- Lokalizacja: Zbąszynek
- Pomógł: 41 razy
Faktory i spójność krawędziowa
Znalazłem twierdzenie, że każdy graf kubiczny bez mostu ma 1-faktor, także nie uda Ci się.