Indukcja matematyczna w grafie.

[Gui]

Potrzebuję formalnego rozwiązania zadania przy pomocy indukcji matematycznej:
"Niech \(\displaystyle{ G}\) będzie grafem rzędu \(\displaystyle{ n \ge 3}\). Udowodnij indukcyjnie, że jeżeli \(\displaystyle{ ||G|| \ge \left\lfloor \frac{ n^{2} }{4} \right\rfloor +1}\), to w grafie \(\displaystyle{ G}\) istnieje podgraf \(\displaystyle{ K_{3}.}\)"
Z góry dziękuję za wszelką pomoc.

[Mruczek]

To jest, bardzo znane, twierdzenie Mantela. Tego jest pełno w internecie. A jeszcze więcej jak wpiszesz Mantel theorem po angielsku.
, zad. 7

Kod: Zaznacz cały

http://www.deltami.edu.pl/temat/matematyka/teoria_grafow/2010/04/27/Rapsodia_pajecza/

37 OM - III - 5: [url]http://archom.ptm.org.pl/?q=node/789[/url]

Btw. Istnieje wiele dowodów tego twierdzenia, nie tylko indukcyjny.