Hogy bizonyítanátok, hogy egy 6 pontú gráfban minimum 8 él kell ahhoz, hogy 2 háromszöget adjon?

Sehogy, mert nem igaz: képzelj el egy négyzetet, aminek az egyik átlója is be van húzva. Ez kiad két háromszöget, és csak öt éle van.

De ha különálló háromszögek kellenek, akkor is elég hat él.

#3

Na de a négyzet az 4 pontból álló gráfnak tekinthető, a feladatban 6 pontú gráf a kérdés.

Szerintem ennek az egésznek csak akkor van értelme, ha az is kikötés a feladatban, hogy minden pont fokszáma legalább 2, vagyis hogy először összekötöd a "szomszédos" pontokat, majd húzol két élt keresztbe, amik így már kiadják a kettő darab háromszöget. Ugye egy élt húzni nem elég, mivel egy hatszögbe egy átló behúzásával legfeljebb egy háromszög képezhető.

#4

És egy hat pontú gráfban nem létezhet négy pontú részgráf?

Kapásból felrajzoltam 6 pontú gráfot 8 éllel, amiből 5 db. háromszög jött ki. De olyat is fel tudok rajzolni, amiben 0 db. háromszög van.

Mi a pontos feladat? Mik a kikötések? Mert szerintem ez az állítás így önmagában nem igaz.

"A háromszög nem csak kör lehet."

Hanem?