szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 28 maja 2016, o 13:08 
Użytkownik

Posty: 811
Wykaż, że w dowolnym grafie liczba wierzchołków stopnia nieparzystego jest parzysta.

Dowód:
p,n - odpowiednio wierzchołki o stopniu parzystym i nieparzystym
z Lematu o uściskach dłoni
\sum_{v \in V(G)} deg(v) = \sum_{v \in V_p(G)}deg(v) + \sum_{v \in V_n(G)} deg(v) = 2|E|
gdzie|E| jest liczbą krawędzi.
Wiemy, że pierwsza suma jest napewno parzysta, zatem druga suma też musi być parzysta, ponieważ prawa strona równania jest parzysta.
Skoro dla każdego wierzchołka w drugiej sumie, jego stopień jest nieparzysty, to aby druga suma była parzysta, musi być parzysta ilość tych wierzchołków.

Czy taki dowód byłby wystarczający?:)
Góra
PostNapisane: 29 maja 2016, o 12:46 
Użytkownik
Jest ok.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 Ile sposobow - wybor trzech liczb, aby suma byla parzysta  Anonymous  2
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie  alamakota  3
 Ilość różnowartościowych niemonotonicznych funkcji.  Anonymous  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl