a): Az 1. eljárás minden lépésben x1 egy szomszédját választja ki, vagy egy már kiválasztott szomszédjának szomszédját (x1 „másodszomszédját”), vagy x1 egy szomszédjának „másodszomszédját (x1 „harmadszomszédját”), stb. Vagyis minden lépésben olyan pontot választ ki, amelybe vezet út x1-bol. Tehát G’ teljesíti az összefüggőség második definícióját. Másrészt minden lépésben egy újonnan választott pontot kötünk össze egy már korábban kiválasztottal, ezért egyetlen beválasztott él sem zárhat be kört a már korábban beválasztott élekkel. A G’ részgráf tehát körmentes és összefüggő, tehát fa.
b): Egy összefüggő gráf bármely két pontja között megy út, ha tehát két még össze nem kötött pontját összekötjük, akkor ez az él kört zár be az él két végpontját már eddig is összekötő úttal.
c) Ha a G gráf nem egyezik a G’ részgráfjával, akkor van olyan éle, amely nem szerepel G’-ben. De akkor b) szerint ez az él kört zár be a G gráfban. Tehát G nem lehet fa. Ha tehát G fa, akkor megegyezik a G’ részgráfjával.
| TARTALOMJEGYZÉK |