Gráf elmèlet feladat??

Ez egy gráfelméleti tétel speciális esete.

A maximális körmentes egyszerű gráf a fa. Egy n-pontú fának n-1 éle van.

Például itt:

[link]

"Ha egy 51 pontu Grafban nincs kor, akkor legfeljebb 50 èle lehet."

Teljes indukció:

- Van egy n csúcsú n élű gráfom, amire igaz, hogy nincs benne kör és nem tudok újabb élt felrakni, anélkül, hogy kör keletkezne.

- Hozzáadok egy pontot és megpróbálok 2 élet felrakni, hogy megtörjem a szabályt. A eredeti gráfba nem tudok kör nélkül új élet berakni. Ezért mindkét élnek az új pontból kell kiindulni és az eredeti (n csúcsú) gráfban végződni. De mivel az eredeti gráf bármely pontjából bármelyikbe el lehetett jutni mielőtt az új éleket beraktam, ezért kör képződne.

- a kiinduló eset: az egy csúcsú gráfnak csak 0 éle lehet, ha nincs benne kör.

"Van egy n csúcsú n élű gráfom, ..."

helyesbítés:

Van egy n csúcsú n-1 élű gráfom, ...