On spanning tree congestion

AbstractWe prove that every connected graph G of order n has a spanning tree T such that for every edge e of T the edge cut defined in G by the vertex sets of the two components of T−e contains at most n32 edges. This result solves a problem posed by Ostrovskii (M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219–226)