podgraf izomorficzny z drzewem
-
kolegasafeta
- Użytkownik
- Posty: 209
- Rejestracja: 26 lis 2009, o 23:45
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 17 razy
- Pomógł: 8 razy
podgraf izomorficzny z drzewem
Niech \(\displaystyle{ T}\) będzie drzewem o \(\displaystyle{ k}\) krawędziach. Udowodnij, że dowolny graf\(\displaystyle{ G}\), którego każdy wierzchołek jest stopnia co najmniej \(\displaystyle{ k}\), zawiera podgraf izomorficzny z drzewem \(\displaystyle{ T}\).