Witam!
Nie mogę wpaść na pomysł rozwiązania następującego zadania:
Graf prosty \(\displaystyle{ G}\) rzędu \(\displaystyle{ n \ge 3.}\)Udowodnij indukcyjnie, że jeśli \(\displaystyle{ \left| \left| G \right| \right| \ge\left[ \frac{ n^2}{4}\right] +1}\) to w grafie \(\displaystyle{ G}\) istnieje podgraf \(\displaystyle{ K_{3}}\).
Sprawdzam, że dla \(\displaystyle{ n=3}\) jest to prawdą, dalej stawiam tezę dla \(\displaystyle{ k}\) i rozpisuję dla \(\displaystyle{ k+1}\), ale nie wiem jak to poprowadzić ? Na rysunku grafu?
Indukcja -graf
-
- Użytkownik
- Posty: 15
- Rejestracja: 28 kwie 2007, o 09:17
- Płeć: Mężczyzna
- Lokalizacja: Staszów
Indukcja -graf
Ostatnio zmieniony 1 kwie 2013, o 22:57 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.