Bridges in highly connected graphs

Let P = {P1,..., Pl} be a set of internally disjoint paths contained in a graph G, and let S be the subgraph defined by ∪ti=1 Pi. A P-bridge is either an edge of G - E(S) with both endpoints in V(S) or a component C of G - V(S) along with all the edges from V(C) to V(S). The attachments of a bridge B are the vertices of V(B) ∪ V(S). A bridge B is k-stable if there does not exist a subset of at most k - 1 paths in P containing every attachment of B. A classic theorem of Tutte [Graph Theory, Addison-Wesley, Menlo Park, CA, 1984] states that if G is a 3-connected graph, there exists a set of internally disjoint paths P′ = {P′1{,..., P′l} such that Pi and P′i have the same endpoints for 1 ≤ i ≤ t and every P′-bridge is 2-stable. We prove that if the graph is sufficiently connected, the paths P′1,..., P′l may be chosen so that every bridge containing at least two edges is, in fact, k-stable. We also give several simple applications of this theorem related to a conjecture of Lovász [Problems in Graph Theory, Recent Advances in Graph Theory, M. Felder, ed., Acadamia, Prague, 1975] on deleting paths while maintaining high connectivity. © 2010 Society for Industrial and Applied Mathematics.