Gráfelmélet kérdés?

Szerintetek így is jó a bizonyítás?

Ha egy G gráfba behúzok egy élt akkor megkapom a G+e gráfot és ez a 2 eset közül pontosan 1 fog igaz lenni:

1. eset:

Ha egy komponensen belül húzok be élt, akkor az egy kört fog létrehozni, mivel egy komponensen önmagában összefüggő, tehát benne bármely 2 csúcs között vezet út, és ha az útnak a 2 végpontját összekötöm, akkor kör jön létre, így az él behúzása kört hoz létre ha azt egy összefüggő komponensen belül húztam be. De ennek az élnek a behúzása nem növeli a komponensek számát, mivel egy komponensen belül húztam be élt, tehát ezzen az élen keresztül nem fog út vezetni egy másik komponensbe sem, így a komponensek száma ugyan annyi marad egy ilyen él behúzása után.

2.eset:

Ha 2 különböző komponens közé húzok be élt, akkor az csökkenti a komponensek számát, mivel a 2 komponens összeolvad, bármely csúcsból bármelyik másikba eltudok majd jutni. Ez az él viszont kört nem hoz létre, mivel ha volna kör a behúzott élen keresztül a gráfban, akkor a körből elhagyva a behúzott élt egy utat kapnék, de a 2 pont között pedig nincs út, mivel azok különböző komponensben vannak.

Az éltörlési lemma ugyanez, csak a fordítottja:

Ha egy élt elhagyok egy G gráfból, megkapom (G-e)-t és 2 dolog történhet:

1. eset:

Ha egy komponensen belül törlök ki egy élt: G-nek és G-e-nek ugyanannyi komponense lesz, de G-e-nek kevesebb kör

2.eset:

Ha két komponens közötti élt törlök ki: G-nek és G-e-nek ugyanannyi köre lesz, de G-e-nek 1-el több komponense lesz

Vagyis ha egy fából 1 élt kitörlök akkor az a fa szétesik 2 komponensre, azaz egy 2 komponensű erdő keletkezik.

Ez azért igaz mert:

Ha egy fából kitörlök egy élt akkor az éltörlési lemmában az 1. eset (a körök száma csökken) az nem valósulhat meg, hisz egy fában 0 kör volt és ennek a száma nem tud csökkeni, tehát ha éltörlést hajtok végre egy fán, akkor mindig a 2. eset valósul meg (azaz ugyanannyi kör marad, de az új gráfnak 1-el több komponense lesz), vagyis mivel a fa az egy összefüggő (1 komponensű gráf) így ha kitörlök belőle egy élt ami növeli a komponensek számát, akkor egy 2 komponensű gráfot fogok kapni

Egy fában bármely 2 csúcs között pontosan 1 út vezet.

Ez azért van, mert:

Egy fában bármely u és v csúcs között létezik út, hiszen a fa az egy összefüggő gráf, tehát bármely u és v csúcs között 1 út biztosan létezik.

Viszont 1-nél több út nem létezik 2 csúcs között, mivel ha létezne 2 út, akkor az azt jelentené, hogy volna 2db uv útunk, és akkor volna olyan él ami az egyik uv úton rajta lenne, a másik uv úton meg nincsen rajta. Tehát lenne a gráfban akkor egy olyan „e” él ami rajta volna az egyik uv úton, de nem volna rajta a másik uv úton.

Ha ezt az „e” élt kitörölném a fából, akkor ebben az esetben a fa 2 komponensre esne szét és az e él 2 végpontja külön komponensbe kerülne. Azonban ez nem történik meg, mert az „e” egyik végpontjából vezet él az „u”-ba, az „u”-ból pedig vezet út a „v”-be, a "v"-ből meg vezet út az „e” él-nek a másik végpontjába. Tehát az „e” él 2 végpontja még sem kerül 2 különböző komponensbe, azaz az „e” él törlésével a gráfom összefüggő marad, nem esik szét 2 komponensre, pedig ha egy fából törlünk 1 élt az 2 komponensre esik szét, ez ellentmondás.

Egy fába ha behúzok egy élt, akkor pontosan 1 kör fog keletkezni

Ez azért igaz, mert:

Ha van egy gráfom és ebbe behúzok egy „e” élt, akkor az olyan körök amik az „e” behúzásával jellenek meg, azok úgy fognak kinézni, hogy az „e” él meg egy út ami összeköti az „e” él 2 végpontját. És akárhogy veszek 2 pontot a fában (mondjuk az „e” él 2 végpontját), pontosan 1 út köti össze őket, ezért amikor az „e” élt behúzom, akkor pontosan 1 kört fogok létrehozni, mert egy útnak össze fogom kötni a 2 végpontját ezzel a behúzott új "e" éllel.

Mit gondoltok, így jó lehet?

Igen, de félek, hogy még abba is belekérdeznek.

"Ha hozzáveszünk egy élt, akkor annak két végpontja között két út lesz, ezek uniója kört ad."

pl.: Miért lesz két végpont közöttkét út, vagy miért ad ezeknek uniója kört