A II/10. feladat megoldása:

Egy kör bármely két szomszédos pontjának távolsága egy, viszont a favázában egy él nem fog szerepelni, ennek két végpontja közötti távolság tehát a favázban nagyobb lesz egynél. Nyilvánvaló, hogy ha az összefüggő gráf nem körmentes, akkor mindig lesz olyan éle, amely nem szerepel a favázban és ennek végpontjai között a favázban egynél nagyobb lesz a távolság.

Tehát ha egy összefüggő gráf nem körmentes (nem fa), akkor nincs a 10. feladat feltételének megfelelő, azaz „távolságtartó” faváz, vagyis olyan faváz, amely a gráf bármely két pontja között megtartja a távolságot.

Most „enyhítünk” a feladat feltételén:

11. feladat:

Van-e olyan faváza minden összefüggő gráfnak, amely egy rögzített x ponttól vett összes távolságot „megtartja”?

MEGOLDÁS