On a conjecture of Bondy and Fan

Abstract

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.