a) Az él két végpontja között nem marad út, hiszen a fában bármely két pont között pontosan egy út van, az él két végpontja között az él volt ez az egyetlen út.
b) A behúzott él két végpontját köti össze út a fában.
c) Ha d(x)=1, akkor az elhagyásával keletkező gráf is fa, mert körmentes gráf részgráfja is körmentes és az elsőfokú pont elhagyásával keletkező részgráf összefüggő marad. Ha viszont x-nek legalább két szomszédja van, legyenek ezek u és v. A fában u és v között is egyetlen út van, s ez az uxv út, amelyet x elhagyásával megszüntetünk. Tehát G–x gráfban u és v között nem fut él, azaz G–x nem lehet összefüggő.
Az olyan pontot, amely elhagyásával az összefüggő gráf megszűnik összefüggő lenni, elvágó pontnak, angol szóval cutpoint-nak nevezzük. A fenti c) állítás tehát azt mondja ki, hogy ha x legalább másodfokú pontja a fának, akkor x elvágó pont.
Igaz-e, hogy ez utóbbi állítás jellemzi a fát? Azaz igaz-e, hogy ha egy összefüggő gráf bármely legalább másodfokú pontja cutpoint, akkor a gráf fa?
| TARTALOMJEGYZÉK |