Megoldás: 3.1
1. megoldás.
Ha két pont össze van kötve éllel, akkor távolságuk 1. A favázban is ennyi kell, hogy legyen a távolságuk, tehát ott is éllel kell összekötve lenniük. Ha
G egyszerű gráf, akkor ebből következik, hogy
G minden éle éle a faváznak is, tehát
G azonos a favázával. Ha
G egyszerű gráf, akkor a feladat feltétele pontosan akkor teljesül, ha
G fa.
Ha
G-ben vannak többszörös élek, akkor annyiban módosul az állítás, hogy
G-t úgy kapjuk egy fából, hogy bizonyos éleit ,,megtöbbszörözzük".
2. megoldás.
Ilyen favázat a következőképpen csinálhatunk. A faváz gyökere az
x pont. Ez lesz a ,,nulladik emelet". A fa ,,első emeletére"
x szomszédainak kell kerülniük, a fához hozzávesszük az
x-szel összekötő éleket. A ,,második emeletre" azoknak a pontoknak kell kerülniük, amelyekből
x kettő távolságra van. Minden ilyen ponthoz kiválasztunk egy-egy,
x-be vezető kettő hosszú utat. Ez nyilván keresztül vezet az ,,első emelet" egy pontján. Vagyis a ,,második emeleten" pontosan azoknak a pontoknak kell szerepelniük, amelyeknek van szomszédjuk az ,,első emeleten", de nem szomszédai
x-nek. A következőre kell figyelnünk: ha egy ilyen pontnak több ,,első emeleti" szomszédja van, ezek közül csak eggyel kötjük össze (mivel favázat keresünk).
Általában is az ,,
i-edik emeletre" azoknak a pontoknak kell kerülniük, amelyek
i távolságra vannak
x-től, tehát
i hosszú úttal elérhetők
x-ből, de rövidebbel nem. Ezek a pontok pontosan azok, amelyek még nem szerepelnek korábbi emeleten, de van szomszédjuk az
i-1-edik emeleten.
A keresett tulajdonsággal rendelkező favázat tehát a következő eljárással kapunk. A ,,nulladik emeleten" csak
x van. Az ,,első emeleten"
x szomszédai. Általában az
i-edik emeleten az
i-1-edik emeleten levő pontok olyan szomszédai, amelyek korábbi emeleten még nem szerepeltek. Minden pontot pontosan egy,
i-1-edik szintű ponttal kötünk össze. A gráf összefüggő, tehát minden ponthoz eljutunk, és az eljárás közben vigyáztunk arra, hogy kör ne keletkezzen, tehát favázat kapunk.