Podgraf o wszystkich wierzchołkach stopnia nieparzystego

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
Konikov
Użytkownik
Użytkownik
Posty: 497
Rejestracja: 13 mar 2008, o 18:56
Płeć: Mężczyzna
Lokalizacja: z całki tego świata
Podziękował: 66 razy
Pomógł: 44 razy

Podgraf o wszystkich wierzchołkach stopnia nieparzystego

Post autor: Konikov » 6 wrz 2010, o 21:56

Udowodnij, że jeśli \(\displaystyle{ 2 | n}\), to dowolny spójny graf \(\displaystyle{ n}\)-wierzchołkowy zawiera podgraf \(\displaystyle{ n}\)-wierzchołkowy, w którym wszystkie wierzchołki mają stopień nieparzysty.

ODPOWIEDZ