OAI.StrongThinTree.strongThinTree

The theorem states that the proposition MainStatement holds. Here a multigraph on n vertices with m edges is given by two endpoint maps from the m edges to the n vertices, with the two endpoints of every edge distinct (no loops, parallel edges allowed). For an edge subset T and a vertex subset S, the cut of T at S is the set of edges in T with exactly one endpoint in S. A subset T is connected if every nonempty proper vertex subset S has at least one edge of T in its cut. T is a spanning tree if it is connected and removing any single edge of T leaves it no longer connected. The graph is k-edge-connected if every nonempty proper vertex subset has at least k edges of the full edge set in its cut. MainStatement asserts that there is a real constant C>0 such that for every integer k≥1, every n≥2, every m and every multigraph G on n vertices with m edges that is k-edge-connected, there exists a spanning tree T of G such that for every nonempty proper vertex subset S, the number of tree edges crossing S is at most (C/k) times the number of edges of G crossing S.