Indukcja matematyczna w grafie.
: 26 kwie 2018, o 17:51
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.
"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.