Feladat: 6.19.
Döntsük el, hogy igaz-e a következő állítás:
Egy összefüggő gráf pontosan akkor fa, ha minden legalább másodfokú pontja elvágó pont.
A fa definícióját lásd a
7.7. feladat után.
Megoldás: 6.19
A
6.18. feladat megoldásában láttuk, hogy fa minden legalább másodfokú pontja elvágó pont.
Visszafele azonban nem igaz az állítás. Lásd a
2.16. feladat megoldásában az ábra bal oldalán szereplő gráfot, és általában bármelyik ,,napsugár" gráfot (egy kör és minden pontjából egy hídél indul egy-egy elsőfokú ponthoz). Ezek mindegyikében minden legalább másodfokú pont elvágó pont.