czy istnieje graf o stopniach wierzchołków
-
- Użytkownik
- Posty: 209
- Rejestracja: 13 lip 2012, o 14:32
- Płeć: Kobieta
- Lokalizacja: Pcim
- Podziękował: 107 razy
czy istnieje graf o stopniach wierzchołków
Jak pokazać, że nie istnieje graf o ciągu stopni wierzchołków \(\displaystyle{ (7,7,7,3,3,3,2,2)}\)?
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
czy istnieje graf o stopniach wierzchołków
Prościej na palcach - skoro wierzchołków jest osiem, a trzy z nich mają mieć stopień \(\displaystyle{ 7}\), to znaczy, że są połączone ze wszystkimi pozostałymi. Stąd wniosek, że wszystkie pozostałe musiałyby mieć stopień co najmniej \(\displaystyle{ 3}\).
Q.
Q.