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

Először is: ugye összefüggő gráfról beszélünk?

Mert különben rajzolok 2 háromszöget, és megvan a 6 pont, de csak 6 él.

Ha összekötöm ezt a 2 háromszöget, akkor az 7 él.

Tehát a feltevésed nem igaz, mert 7 él elég.

Ignorálva azt a megjegyzést, hogy háromszög nem csak kör lehet, még most se igaz.

o--o--o

| | |

| | |

o--o--o

Plusz a két átlót is húzzuk be. Ennek kilenc éle is van, és egy háromszög sincs benne.

Namégegyszer:

o--o--o

| | |

| | |

o--o--o

Ha valaki rájön, hogy mi haszna van annak, hogy az előnézetben más betűtípussal jelenik meg a válasz, mint posztolás után, írjon egy privátot.

Vagy ha arra jön rá, hogy miért veszi ki a szóközöket a rendszer, vagy ha már igen, miért nem figyelmeztet erre, vagy ha már nem, miért nem lehet korábbi választ törölni vagy szerkeszteni.

Leírom akkor szóban: egy 2×3-as téglalapot próbáltam rajzolni, aminek az (1,2) és a (2,2) csúcsai között is fut él, és a két átló ((1,1)-(2,3) & (1,3)-(2,1)) is be van húzva.

A kérdező a kezdetektől fogva 8 élről beszélt és a pontosítás* után amúgy így már tényleg igaz a bizonyítandó állítás, hiszen a 8. élt már csak átlóba lehet behúzni, amiből rögtön két háromszög keletkezik. Igazából ha ezt így lerajzolja, akkor azzal már el van kezdve a bizonyítás, már csak be kell látni, hogy ez a pontok bármilyen elrendezése esetén is megállja a helyét.

Esetleg ebből ki lehet indulni:

[link]

* "Egy 6 pontú gráfban ha 8 él van, biztos, hogy van MINIMUM 2 háromszög."