Faktory i spójność krawędziowa

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
rubik1990
Użytkownik
Użytkownik
Posty: 520
Rejestracja: 28 sty 2009, o 19:39
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 14 razy
Pomógł: 86 razy

Faktory i spójność krawędziowa

Post autor: rubik1990 »

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
szatkus
Użytkownik
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

Post autor: szatkus »

Znalazłem twierdzenie, że każdy graf kubiczny bez mostu ma 1-faktor, także nie uda Ci się.
ODPOWIEDZ