Indukcja -graf

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
diablomichal
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 28 kwie 2007, o 09:17
Płeć: Mężczyzna
Lokalizacja: Staszów

Indukcja -graf

Post autor: diablomichal »

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?
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.
ODPOWIEDZ