1. Does there exist a function $f: \mathbf{N} \to \mathbf{N}$ such that every $f(k)$-vertex-connected graph $G$ can have its edges partitioned into two spanning subgraphs $G_1$, $G_2$ such that both of them are $k$-vertex-connected?
  2. If so, can $f(k)$ be chosen linear in $k$?

For the record, I know the answer to both questions is "yes" when we ask for edge-connectivity instead. We may take $f(k) = 4k$. Every $4k$-edge-connected graph has $2k$ disjoint spanning trees (see, e.g. here). We define edge-disjoint subgraphs $G_1$, $G_2$ of $G$ such that each $G_i$ contains at least $k$ of the spanning trees; and we assign every remaining edge arbitrarily either to $G_1$ or $G_2$. Since each $G_i$ has at least $k$ disjoint spanning trees, it must be $k$-edge-connected.

Update: An open conjecture due to Kriesell states that there exists a function $f(k)$ such that every $f(k)$-vertex-connected graph has a spanning tree whose removal gives a $k$-vertex-connected graph. This is only known to be true for $k \leq 2$. That is, in general it is not even known how to decompose highly connected graphs into a $1$-connected and a $k$-connected spanning graphs; let alone two $k$-connected spanning subgraphs. So my question, if true, is an open problem. But it is still possible that my question might be answered in the negative with a simple counterexample, which would also be interesting.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.