Indukcja -graf
: 1 kwie 2013, o 22:17
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?
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?