Megoldás: 6.20
1. megoldás.
Igaz. Vegyük a gráf egy
P leghosszabb útját és tekintsük ennek egyik
v végpontját. Ennek a pontnak minden szomszédja a
P pontja, tehát
v bármely két szomszédját köti össze olyan út, amely elkerüli
v-t. (Ha
v elsőfokú, akkor az állításunk semmitmondóan igaz.) Ez viszont azt jelenti, hogy
v elhagyása után bármely két pont között vezet út, ha előtte is vezetett.
2. megoldás.
Igaz. Vegyük a gráf egy favázát. Ennek bármely elsőfokú pontját elhagyva a gráfból összefüggő gráf marad, hiszen már a faváza is megmarad.