Publication
Journal of Combinatorial Theory, Series B
Paper

Bounds on the number of disjoint spanning trees

View publication

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.

Date

Publication

Journal of Combinatorial Theory, Series B

Authors

Share