graf-nieparzysta ilosc wierzchołków nieparzystego stopnia

mateuss · Post autor: **mateuss** » 12 kwie 2008, o 14:36

Czy ktos potrafi podac dowód do zadania:
Czy graf moze miec nieparzysta ilosc wierzchołków nieparzystego stopnia?
Narazie doszedłem do tego, ze nie, bo:
Pomijajac petle bo nie maja one wpływu na parzystosc/nieparzystosc mozna zauwazyc, ze kazda krawedź łaczy 2 wierchołki, a z tego wynika... i na tym niestety koniec mojego rozumowania

UNIX_admin · Post autor: **UNIX_admin** » 12 kwie 2008, o 14:57

suma stopni wierzcholkow jest liczba parzysta (poniewaz jest rowna 2*liczba krawedzi), a sumujac nieparzyscie wiele liczb nieparzystych dostajemy liczbe nieparzytsta wiec sprzecznosc. bardziej formalny dowod znajdziesz w kazdej ksiazce z zakresu teorii grafow.

mateuss · Post autor: **mateuss** » 12 kwie 2008, o 15:28

dzieki