Redundant Trees in Bipartite Graphs

It has been conjectured that for each positive integer k and each tree T with bipartite (Z1,Z2), every k-connected bipartite graph G with δ(G)≥k+max{|Z1|,|Z2|} admits a subgraph T′≅T such that G−V(T′) is still k-connected. In this paper, we generalize the ear decompositions of 2-connected graphs into a (k,ak)-extensible system for a general k-connected graph. As a result, we confirm the conjecture for k≤3 by proving a slightly stronger version of it.