Bondy and Fan recently conjectured that if we associate non-negative real weights to the edges of a graph so that the sum of the edge weights is \(W\), then the graph contains a path whose weight is at least \(\frac{2W}{n}\). We prove this conjecture.
Citation
Alan Frieze, Colin McDiarmid, Bruce Reed. On a conjecture of Bondy and Fan[J], Ars Combinatoria, Volume 033. 329-336. .