High connectivity keeping spanning trees
(suggested by Matthias Kriesell)
It is an old question, attributed to L. Lovász , to decide whether for every k > 0 there exists a (smallest) f(k) such that in between any two vertices of an f(k)-connected graph G there exists an [induced] path P such that G - V(P) is k-connected. It is known that f(1) = 3 and f(2) = 5 (see ), whereas the existence of f(k) for any k > 2 is open. Some years ago I suggested to relax the question as follows: For every k > 0 there exists a (smallest) g(k) such that in between any two vertices of an g(k)-connected graph G there exists an [induced] path P such that G - E(P) is k-connected; this has been proven in , with g(k) ≤ ck2 for some constant c < 2000; it would follow from an affirmative answer to the following.
Conjecture: For every k > 0 there exists a (smallest) h(k) such that every h(k)-connected graph has a spanning tree T such that G - E(T) is k-connected.
What is known?
The analogue for edge-connectivity follows easily from Tutte's and Nash-Williams's base packing theorem (and yields h(1) = 4). By a result of T. Jordán on rigid bases , every 6k-connected graph has k edge-disjoint spanning 2-connected subgraphs, implying h(2) ≤ 12, which has been improved to h(2) ≤ 8 recently . The existence of h(k) for any k > 2 is wide open.
 J. Cheriyan, O. Durand de Gevigney, and Z. Szigeti, Packing of rigid spanning subgraphs and spanning trees, J. Combin. Theory Ser. B 105 (2014), 17-25.
 T. Jordán, On the existence of k edge-disjoint 2-connected spanning subgraphs, J. Combin. Theory Ser. B. 95 (2005), 257-262.
 K. Kawarabayashi, O. Lee, B. Reed, and P. Wollan, A Weaker Version of Lovász Path Removal Conjecture, J. Combin. Theory Ser. B 98 (2008), 972-979.
 M. Kriesell, Induced paths in 5-connected graphs, J. Graph Theory 36 (2001), 52-58.
 C. Thomassen, Graph decompositions with applications to subdivisions and path systems modulo k, J. Graph Theory 7 (1983), 261-271.
Please add comments here
I recall hearing another problem on digraphs. Is there a function f(k) such that any f(k)-edge-connected digraph has k-edge-disjoint strongly-connected digraphs? It appears that one can prove a weak version where one says that if a digraph is (ck log n)-edge-connected (here c is some fixed constant) then there are k edge-disjoint strongly-connected digraphs. Is this interesting and/or known?