Bounds on the number of disjoint spanning trees

Abstract

It is shown that an n-edge connected graph has at least ⌈ (n - 1) 2⌉ pairwise edge-disjoint spanning trees. This bound is best possible in general. A maximal planar graph with four or more vertices contains two edge-disjoint spanning trees. For a maximal toroidal graph, this number is three. © 1974.