Egy n csúcsú teljes gráf minden élének más a súlya? Bizonyítsuk be, hogy csak egy minimális összsúlyú feszítőfája van!

> Bizonyítsuk be, hogy csak egy minimális összsúlyú feszítőfája van!

[link]

Itt szerepel a bizonyítás a Tulajdonságai/Multiplicitás résznél.

> Hogyan súlyozzuk egy n csúcsú teljes gráf éleit úgy, hogy a súlyok össze 1, és a minimális súlyú feszítőfa a lehető legnagyobb?

Mindegyik élre ugyanakkora súlyt kell rakni.

> Mennyi az így kapott minimális feszítőfa súlya?

1/(n*(n-1)/2) él van, egy feszítőfában (n-1), tehát 2/n súlyú egy ilyen.

> Hogyan súlyozzuk egy n csúcsú teljes gráf éleit úgy, hogy a súlyok össze 1, és a minimális súlyú feszítőfa a lehető legnagyobb?

Az nyilvánvaló hogy ha van olyan feszítőfa amelyik 2/n-nél nehezebb, akkor van nála könnyebb is (hiszen a feszítőfák összsúlya független a súlyozástól).

Elég tehát megmutatni, hogy az egyetlen súlyozás ahol minden feszítőfa súlya 2/n, az az, hogy minden él ugyanakkora súlyt kap. Ez például a wikipédián írt gondolatmenetből nagyon egyszerűen adódik. (Tegyük fel hogy létezik két eltérő él, ...)