Highly connected graphs have highly connected spanning bipartite subgraphs

Abstract

For integers $k,n$ with $1\leq k\leq n/2$, let $f(k,n)$ be the smallest integer $t$ such that every $t$-connected $n$-vertex graph has a spanning bipartite $k$-connected subgraph. A conjecture of Thomassen asserts that $f(k,n)$ is upper bounded by some function of $k$. The best upper bound for $f(k,n)$ is by Delcourt and Ferber who proved that $f(k,n)\leq 10^{10}k^{3}\log n$. Here it is proved that $f(k,n)\leq 22k^{2}\log n$. For larger $k$, stronger bounds hold. In the linear regime, it is proved that for any $0<c<\frac{1}{2}$ and all sufficiently large $n$, if $k=\lfloor cn\rfloor$, then $f(k,n)\leq 30\sqrt{c}n\leq 30\sqrt{n(k+1)}$. In the polynomial regime, it is proved that for any $\frac{1}{3}\leq\alpha<1$ and all sufficiently large $n$, if $k=\lfloor n^{\alpha}\rfloor$, then $f(k,n)\leq 9n^{(1+\alpha)/2}\leq 9\sqrt{n(k+1)}$.

AMS subject classifications: 05C35, 05C40
Keywords: connectivity; bipartite; spanning

1 Introduction

All graphs and digraphs considered here are finite and simple. For $k\geq 1$, a graph $G$ is $k$-connected if it has at least $k+1$ vertices, but does not contain a set of $k-1$ vertices whose removal disconnects $G$. Let $\kappa(G)$ be the largest $k$ such that $G$ is $k$-connected.

The study of $k$-connectivity and $\kappa(G)$ are central in graph theory with several classical results relating properties of $G$ to its $k$-connectivity or to the $k$-connectivity of a subgraph of $G$. One such result is a theorem of Mader [8] that any graph with $n$ vertices and at least $2kn$ edges has a $k$-connected subgraph. For large $n$, the constant $2$ can be replaced with $\frac{19}{12}$ as proved by Bernshteyn and Kostochka [2], improving an earlier result of the author [13], and arriving close to Mader’s conjectured optimal value of $\frac{3}{2}$ [9]. As any graph has a bipartite subgraph with at least half the number of edges, it follows that any graph with at least, say, $4kn$ edges contains a bipartite $k$-connected subgraph. But what if we require the subgraph to be spanning? As observed by Thomassen, if $G$ is $2k-1$ edge-connected (a graph is $t$ edge-connected if one must remove at least $t$ edges to disconnect it), then every maximum edge cut (which, in turn, is a spanning bipartite subgraph) is $k$ edge-connected. A longstanding conjecture of Thomassen [12] asserts that a similar statement (replacing $2k-1$ with any function of $k$) should hold for $k$-connectivity. Let us be more formal regarding this problem, as we are addressing it for $k$ that may depend on the number of vertices of $G$.

For integers $k,n$ with $1\leq k\leq n/2$, let $f(k,n)$ be the smallest integer $t$ such that every $t$-connected $n$-vertex graph has a spanning bipartite $k$-connected subgraph. It is clear that $f(1,n)=1$ as shown by taking any spanning tree. It is also clear that the requirement $k\leq n/2$ is necessary. Indeed, $\kappa(H)\leq n/2$ for any bipartite graph $H$ with $n$ vertices. Also notice that $f(k,n)\leq n-1$ as $K_{n}$ is $(n-1)$-connected. It is also not difficult to prove that $f(2,n)=3$ for all $n\geq 5$ (see Section 3 for such a proof). Thomassen’s conjecture states that $f(k,n)$ is upper bounded by some function of $k$.

The presently best upper bound on $f(k,n)$ is by Delcourt and Ferber [4] who proved that $f(k,n)\leq 10^{10}k^{3}\log n$ . While this does not prove Thomassen’s conjecture, it does show that the dependence on $n$ is at most logarithmic. It should be noted that Delcourt and Ferber explicitly state that their main focus is the dependence on $n$ and not the dependence on $k$. Nevertheless, the problem is intriguing also for large $k$ that depends on $n$. For example, is it true that if $G$ has linear connectivity, then it has a spanning bipartite subgraph of reasonable linear connectivity? Here we give a positive answer to this question and significantly improve the dependence on $k$ and the absolute constants in all regimes.

Theorem 1.1.

(a) For all $1\leq k\leq n/2$, $f(k,n)\leq 22k^{2}\log n$.
(b) For all $0\leq\alpha<1$ and sufficiently large $n$, if $k=\lfloor n^{\alpha}\rfloor$, then $f(k,n)\leq 9n^{(1+\alpha)/2}\leq 9\sqrt{n(k+1)}$.
(c) For all $0<c<\frac{1}{2}$ and sufficiently large $n$, if $k=\lfloor cn\rfloor$, then $f(k,n)\leq 30\sqrt{c}n\leq 30\sqrt{n(k+1)}$.

Note that while the constant $c$ in Item (c) covers every possible value, it is only meaningful if $c<\frac{1}{900}$ since we always have $f(k,n)\leq n-1$.

It should be noted that Theorem 1.1 does not shed more light on Thomassen’s conjecture as the dependence on $n$ in Case (a) is still logarithmic as in [4]. On the other hand, it scales the dependence on $k$ from at most quadratic to ever smaller polynomials as $k$ grows beyond $n^{1/3}$. We also note that while we did not try to optimize the absolute constants, they are reasonably small.

Finally, we note that problem addressed here falls under the following general paradigm (see Perarnau and Reed [10]). Given a graph parameter $\rho$, a value $k$, and a family of graphs ${\mathcal{F}}$, determine the largest value of $\ell$ such that for every graph $G$ with $\rho(G)\geq k$ there exists an ${\mathcal{F}}$-free subgraph $H$ of $G$ with $\rho(H)\geq\ell$. In our case $\rho=\kappa$ and ${\mathcal{F}}$ is the family of odd cycles. Some interesting results following under this paradigm are [3, 5, 6, 7, 10, 11].

2 Proof of Theorem 1.1

Our proof of Theorem 1.1 is an adaptation of the method of Delcourt and Ferber, but with several changes. In particular, we rely on their lemma on subgraph connectivity of digraphs with high minimum out-degree (Lemma 2.1 below), but we do not rely on Mader’s Theorem (the one mentioned in the introduction) which makes the choices of our maximum counter-example (which we use for contradiction) more economical, and resulting in meaningful bounds also when $k$ is large.

We first need the following simple and useful lemma from [4]. For a directed graph $D$ and a vertex $v\in V(D)$, let $d^{+}_{D}(v)$ denote the out-degree of $v$ in $D$ and let $U(D)$ denote the underlying graph of $D$ which is the undirected graph obtained by ignoring the directions of the edges (each cycle of length $2$, which is possible in $D$, corresponds to a single edge in $U(D)$).

Lemma 2.1 ([4]).

If $D$ is a digraph on at most $n$ vertices and with minimum out-degree larger than $(k-1)\log n$, then it contains a subdigraph $D^{\prime}$ with $\kappa(U(D^{\prime}))\geq k$ and where $d^{+}_{D^{\prime}}(v)\geq d^{+}_{D}(v)-(k-1)\log n$ for all $v\in V(D^{\prime})$. ∎

Lemma 2.2.

Let $G_{1}$ and $G_{2}$ be two vertex-disjoint bipartite $k$-connected subgraphs of a graph $G$. If there are at least $2k-1$ pairwise vertex-disjoint edges of $G$ each having an endpoint in $G_{1}$ and an endpoint in $G_{2}$, then one can pick $k$ of these edges such that the union of $G_{1}$ and $G_{2}$, together with the $k$ picked edges, forms a bipartite $k$-connected subgraph of $G$.

Proof.

Let $(A_{1},A_{2})$ be a proper bipartition of $V(G_{1})$ and let $(A_{3},A_{4})$ be a proper bipartition of $V(G_{2})$. Let $F$ be $2k-1$ pairwise vertex-disjoint edges, each with an endpoint in $G_{1}$ and an endpoint in $G_{2}$. Let $F_{i,j}$ be the subset of $F$ consisting of the edges with one endpoint in $A_{i}$ and the other in $A_{j}$. Note that $F$ is the disjoint union of $F_{1,3},F_{1,4},F_{2,3},F_{2,4}$. So either $|F_{1,3}\cup F_{2,4}|\geq k$ or $|F_{1,4}\cup F_{2,3}|\geq k$. In the former case, we can take $F_{1,3}\cup F_{2,4}$ and the union of $G_{1}$ and $G_{2}$ to form a bipartite graph with proper bipartition $(A_{1}\cup A_{4},A_{2}\cup A_{3})$. In the latter case, we can take $F_{1,4}\cup F_{2,3}$ and the union of $G_{1}$ and $G_{2}$ to form a bipartite graph with proper bipartition $(A_{1}\cup A_{3},A_{2}\cup A_{4})$. In any case, the obtained union is $k$-connected as the removal of any $k-1$ vertices keeps $G_{1}$ and $G_{2}$ connected and at least one of the connecting edges is still intact so the union remains connected as well. ∎

Lemma 2.3.

Let $G_{1}$ be a bipartite $k$-connected subgraph of a graph $G$. If there is a vertex $v$ of $G$ outside $G_{1}$ with at least $2k-1$ neighbors in $G_{1}$, then one can pick $k$ of these neighbors such that the union of $G_{1}$ and $v$, together with the $k$ edges connecting $v$ to the picked neighbors, forms a bipartite $k$-connected subgraph of $G$. ∎

Proof.

Let $(A_{1},A_{2})$ be a proper bipartition of $V(G_{1})$ where, without loss of generality, $v$ has at least $k$ neighbors in $A_{1}$. Taking $G_{1}$ together with $v$ and the $k$ edges connecting $v$ to $A_{1}$ gives a bipartite graph with bipartition $(A_{1},A_{2}\cup\{v\})$ which is clearly $k$-connected. ∎

We begin by proving Case (a) of Theorem 1.1. We then show how to modify the proof to obtain the other cases.

Proof of Theorem 1.1, Case (a).

Recall that we must prove that $f(k,n)\leq 22k^{2}\log n$. We assume $k\geq 3$ (as $k=1$ is trivial and $k=2$ follows form Proposition 3.1). Let $s=\lfloor 22k^{2}\log n\rfloor$. We may assume that $s\leq n-1$ since $f(k,n)\leq n-1$. Let $G$ be an $s$-connected graph with $n$ vertices. We prove that $G$ has a bipartite spanning $k$-connected subgraph.

Let $d=\lfloor s/4\rfloor\geq k$. Consider a partition of the vertex set of $G$ into parts $V_{1},\ldots,V_{t}$ such that each $V_{i}$ is either a singleton or else $|V_{i}|\geq d$ and $G[V_{i}]$ has a bipartite spanning subgraph $B_{i}$ that is $k$-connected (for convenience, when $V_{i}$ is a singleton, let $B_{i}$ denote the graph with a single vertex; it is “bipartite” with one part of the bipartition being empty). Hereafter we shall consider a partition $P=\{V_{1},\ldots,V_{t}\}$ where $t$ is minimum and show that we must have $t=1$, concluding the proof. So, assume that $t>1$.

Suppose $V_{i}\in P$ is not a singleton (so $n>|V_{i}|\geq d$). Let $M_{i}$ be a maximum matching of the edge cut $(V_{i},V(G)\setminus V_{i})$. We must have $|M_{i}|\geq d$ as otherwise the $2|M_{i}|\leq 2d-2\leq s-1$ vertices of the endpoints of $M_{i}$, once removed from $G$, disconnect the remaining vertices of $V_{i}$ from the remaining vertices of $V(G)\setminus V_{i}$, contradicting the $s$-connectivity of $G$. Let $S_{i}\subseteq M_{i}$ be such that for any $j\neq i$, there is a single edge incident with $V_{j}$, if such an edge exists. By Lemma 2.2, $|S_{i}|\geq|M_{i}|/(2k-2)\geq d/(2k-2)$ as otherwise $t$ would not be minimum.

Next, suppose that $V_{i}=\{v\}\in P$ is a singleton. We say that $V_{i}$ is of type $\alpha$ if $v$ has at least $3d$ neighbors in $V$, where each of them is a singleton part of $P$. Otherwise, we say that $V_{i}$ is of type $\beta$. Now, if $V_{i}$ is of type $\alpha$, let $S_{i}$ be a set $3d$ edges connecting $v$ to $3d$ singleton parts of $P$. Suppose now that $V_{i}$ is of type $\beta$. As the degree of $v$ in $G$ is at least $s$, we have that at least $s-3d$ edges connect $v$ to non-singleton parts of $P$. By Lemma 2.3 and as $t$ is minimum, at most $2k-2$ such edges connect $v$ to the same non-singleton part of $P$. Thus, there is a set $S_{i}$ of edges connecting $v$ to non-singleton parts of $P$ such that no two edges of $S_{i}$ are incident with the same part and $|S_{i}|\geq(s-3d)/(2k-2)\geq d/(2k-2)$.

To summarize, for each part $V_{i}\in P$ we have chosen a set of edges $S_{i}$ incident to that part and connecting it to other parts, such than no other part $V_{j}$ has more than one vertex incident with $S_{i}$. If $V_{i}$ is non-singleton, then $S_{i}$ is a matching and if $V_{i}$ is a singleton, then $S_{i}$ is a star. In all cases, $t-1\geq|S_{i}|\geq d/(2k-2)\geq(s-3)/(8k-8)>s/8k$ and if $S_{i}$ is a singleton of type $\alpha$, then $|S_{i}|=3d$.

Independently for each $i$, take a random red-blue proper vertex coloring of the bipartite graph $B_{i}$ (so either one part of the bipartition of $B_{i}$ is red and the other part is blue, or vice versa). Once making these $t$ choices, let $T_{i}\subseteq S_{i}$ be those edges whose endpoints have different colors. Observe that the union of all $B_{1},\ldots,B_{t}$ and the edge sets $T_{1},\ldots,T_{t}$ is a bipartite spanning subgraph of $G$. As $|T_{i}|$ has distribution ${\rm Bin}(|S_{i}|,\frac{1}{2})$ we have by Chernoff’s inequality,

$$\Pr\left[|T_{i}|<\frac{|S_{i}|}{4}\right]=\Pr\left[|T_{i}|-{\mathbb{E}}[|T_{i}|]<-\frac{|S_{i}|}{4}\right]<e^{-\frac{2(|S_{i}|/4)^{2}}{|S_{i}|}}=e^{-\frac{|S_{i}|}{8}}\leq e^{-\frac{s}{64k}}\;.$$ (1)

Since $t\leq n$ and since $s>64k\ln n$, we have from (1) and the union bound that with positive probability, $|T_{i}|\geq|S_{i}|/4$ for all $1\leq i\leq t$. Hereafter, we shall assume that this is indeed the case.

We construct a directed graph $D$ on vertex set $[t]$ where $(i,j)$ is an edge whenever $T_{i}$ is incident with a vertex of $V_{j}$. Notice that the out-degree of $i$ is precisely $|T_{i}|\geq|S_{i}|/4>s/32k$. Since $s\geq 32k(k-1)\log n$, we have that $|T_{i}|>(k-1)\log n$ so by Lemma 2.1, $D$ has a subdigraph $D^{\prime}$ on vertex set $V(D^{\prime})\subseteq[t]$ such that $U(D^{\prime})$ is $k$-connected and for each $i\in V(D^{\prime})$ we have $d^{+}_{D^{\prime}}(i)\geq|T_{i}|-(k-1)\log n$. For $i\in V(D^{\prime})$, let $T_{i}^{*}\subseteq T_{i}$ be the set of edges in $T_{i}$ incident with some $V_{j}$ where $j\neq i$ and $j\in V(D^{\prime})$. Notice that $|T_{i}^{*}|=d^{+}_{D^{\prime}}(i)\geq|T_{i}|-(k-1)\log n$.

Consider the bipartite graph $B$ obtained by taking the union of all $B_{i}$ for $i\in V(D^{\prime})$ and all edge sets $T_{i}^{*}$ for $i\in V(D^{\prime})$. First notice that $|V(B)|\geq d$. Indeed, either some $i\in V(D^{\prime})$ is such that $V_{i}$ is not a singleton (so already $|V_{i}|\geq d$), or else for all $i\in V(D^{\prime})$ we have that $|V_{i}|$ is a singleton. But in the latter case, all these singletons must be of type $\alpha$ (if $V_{i}$ is of type $\beta$, then any edge $(i,j)$ in $D^{\prime}$ is such that $V_{j}$ is non-singleton). However, recall that if $V_{i}$ is of type $\alpha$, then $|S_{i}|\geq 3d$ which means that $|T_{i}|\geq 3d/4$. So

$$|T_{i}^{*}|=d^{+}_{D^{\prime}}(i)\geq|T_{i}|-(k-1)\log n\geq\frac{3d}{4}-\frac{s}{32k}\geq\frac{3d}{4}-\frac{4d+4}{32k}\geq\frac{d}{2}$$ (2)

and thus $B$ is a bipartite graph with minimum degree at least $d/2$ so it has at least $d$ vertices.

We will prove that $B$ is $k$-connected. Note that once we do that, we arrive at a contradiction, as the number of parts of the partition obtained by replacing all the parts of $P$ of the form $V_{i}$ with $i\in V(D^{\prime})$ with the single element $V(B)$, is smaller than $t$.

To prove that $B$ is $k$-connected, consider some set $K$ of $k-1$ vertices of $B$. We must show that $B^{*}$, the graph remaining from $B$ after removing $K$, remains connected. Suppose $x\in V_{i}$ and $y\in V_{j}$ (possibly $i=j$) are two vertices of $B^{*}$. We must show that there is a path in $B^{*}$ connecting them. Now, if $i=j$, then $B_{i}[V_{i}\setminus K]$ is connected since $B_{i}$ is $k$-connected. Hence, there is a path between $x$ and $y$ entirely inside $B_{i}[V_{i}\setminus K]$. Assume therefore that $i\neq j$. Let $L=\{\ell\in V(D^{\prime})~{}|~{}V_{\ell}\cap K\neq\emptyset\}$. As $U(D^{\prime})$ is $k$-connected, removing the vertices of $L$ from $D^{\prime}$ keeps $U(D^{\prime}[V(D^{\prime})\setminus L])$ connected. It therefore suffices to show that there is a (possibly trivial) path connecting $x$ to some vertex of $V_{m}$ where $m\notin L$ and there is a (possibly trivial) path connecting $y$ to some vertex of $V_{m^{*}}$ where $m^{*}\notin L$. As the two claims are identical, we prove it for $x$. Notice that the claimed path trivially exists if $i\notin L$. If, however $i\in L$ (namely, some of the vertices of $K$ are in $V_{i}$), then $V_{i}$ cannot be a singleton (as it contains both $x$ and a vertex of $K$). So, $T_{i}^{*}$ is matching of size at least $k$ (since $U(D^{\prime})$ is $k$-connected, its minimum degree is at least $k$). Hence, at least one edge of $T_{i}^{*}$ is not incident with $K$ nor with $V_{\ell}$ where $\ell\in L$. Such an edge is of the form $uv$ where $u\in V_{i}\setminus K$ (possibly $u=x$) and $v\in V_{m}$ with $m\notin L$. As there is a path in $B_{i}[V_{i}\setminus K]$ between $x$ and $u$, the claim follows. ∎

Proof of Theorem 1.1, Case (b).

Recall that we must prove that for all $0\leq\alpha<1$ and sufficiently large $n$, if $k=\lfloor n^{\alpha}\rfloor$, then $f(k,n)\leq 9n^{(1+\alpha)/2}$. The proof is very similar to Case (a). We use the same notation and outline the differences. Set $s=\lfloor 9n^{(1+\alpha)/2}\rfloor$ and let $k=\lfloor n^{\alpha}\rfloor$. We set $d=\lfloor s/4\rfloor\geq k$ and use a partition $P=\{V_{1},\ldots,V_{t}\}$ where $t$ is minimum, as in Case (a), aiming to prove that $t=1$. Assume, to the contrary, that $t>1$. Let $t^{*}$ denote the number of non-singleton parts (i.e. those of size at least $d$) and observe that $t^{*}\leq n/d\leq 4n/(s-3)<n^{(1-\alpha)/2}/2$.

Suppose $V_{i}\in P$ is not a singleton and recall that we have defined $M_{i}$ to be a maximum matching of the edge cut $(V_{i},V(G)\setminus V_{i})$ and that as in Case (a) we have $|M_{i}|\geq d$. By Lemma 2.2, at most $(2k-2)t^{*}$ edges of $M_{i}$ are incident with non-singleton parts, so after removing them from $M_{i}$ we obtain a subset $S_{i}$ with $|S_{i}|\geq d-(2k-2)t^{*}\geq 2n^{(1+\alpha)/2}-2n^{\alpha}n^{(1-\alpha)/2}/2\geq n^{(1+\alpha)/2}$. Notice that this definition of $S_{i}$ is slightly different from the one used in Case (a), as we may take advantage of the fact that there are many singleton parts.

Consider now a singleton part $V_{i}$ and recall that if $V_{i}$ is of type $\alpha$, then $S_{i}$ is the set of edges of a star connecting $V_{i}$ only to singleton parts and $|S_{i}|=3d$. We claim that there are no singletons of type $\beta$. Suppose that $V_{i}$ is of type $\beta$, i.e., at least $s-3d$ edges connect it to non-singleton parts. However, by Lemma 2.3 at most $(2k-2)t^{*}$ edges connect it to non-singleton parts, which is impossible since $(2k-2)t^{*}<n^{(1+\alpha)/2}<s-3d$.

We observe that as in (1), we have that $\Pr\left[|T_{i}|<|S_{i}|/4\right]<e^{-\frac{|S_{i}|}{8}}$ and since $|S_{i}|/8=\omega(\ln n)$, we have that $|T_{i}|\geq\frac{|S_{i}|}{4}$ holds for all $1\leq i\leq t$ with positive probability, so we assume this is the case. Thus, we have that in the directed graph $D$, the out-degree of $i$ is $|T_{i}|\geq|S_{i}|/4\geq n^{(1+\alpha)/2}/4>(k-1)\log n$. We therefore apply Lemma 2.1 to obtain $D^{\prime}$ as in Case (a). The analogue of (2), which, recall, is only applied when $V_{i}$ is of type $\alpha$, now becomes

$$|T_{i}^{*}|=d^{+}_{D^{\prime}}(i)\geq|T_{i}|-(k-1)\log n\geq\frac{3d}{4}-n^{\alpha}\log n\geq\frac{3d}{4}-\frac{d}{4}\geq\frac{d}{2}$$

so, as in Case (a), $|V(B)|\geq d$, the new partition has fewer parts than $P$, and $B$ is $k$-connected, contradicting the minimality of $t$. ∎

Prior to proving Case (c) of Theorem 1.1, we require the following variant of Lemma 2.1.

Lemma 2.4.

Let $0<c<\frac{1}{2}$. For all sufficiently large $n$, if $D$ is a digraph on at most $n$ vertices and with minimum out-degree at least $3c\log(1/c)n$, then it contains a subdigraph $D^{\prime}$ with $\kappa(U(D^{\prime}))\geq cn$ and where $d^{+}_{D^{\prime}}(v)\geq d^{+}_{D}(v)-2c\log(1/c)n$ for all $v\in V(D^{\prime})$.

Proof.

Let $\gamma=3c\log(1/c)$. If $\gamma\geq 1$ or if $\kappa(U(D))\geq cn$, there is nothing to prove. So, assume that $\gamma<1$ and that $\kappa(U(D))<cn$. Delete a separating set of size at most $cn$. The smallest component, denoted by $A$, has fewer than $n/2$ vertices and for any $v\in V(A)$, every out-neighbor of $v$ is either in $V(A)$ or in the separating set that we removed. Hence, $d^{+}_{A}(v)\geq d^{+}_{D}(v)-cn$. We repeatedly apply this step, and note that this process must terminate. However, after step $r=\lceil\gamma/2c\rceil$, we are left with a component which consists of fewer than $n/2^{r}$ vertices where each of these vertices has out-degree at least $\gamma n-rcn$. However, this is impossible since

$$\gamma-rc=\gamma-c\left\lceil\frac{\gamma}{2c}\right\rceil\geq\frac{\gamma}{2}-c\geq\frac{\gamma}{6}\geq c^{3/2}=2^{1.5\log c}=2^{-\frac{\gamma}{2c}}\geq 2^{-r}\;.$$

Thus, the process ends after at most $r-1$ steps, finding the desired $D^{\prime}$ and we have $d^{+}_{D^{\prime}}(v)\geq d^{+}_{D}(v)-(r-1)cn\geq d^{+}_{D}(v)-(\gamma/2)n\geq d^{+}_{D}(v)-2c\log(1/c)n$ for all $v\in V(D^{\prime})$. ∎

Proof of Theorem 1.1, Case (c).

Recall that we must prove that for all $0<c<\frac{1}{2}$ and sufficiently large $n$, if $k=\lfloor cn\rfloor$, then $f(k,n)\leq 30\sqrt{c}n$. The proof is similar to Case (b). We use the same notation and outline the differences. Let $c^{*}=30\sqrt{c}$ and observe that Case (c) holds vacuously when $c\geq 1/900$, hence we assume that $c<1/900$. let $k=\lfloor cn\rfloor$, $s=\lfloor c^{*}n\rfloor$, $d=\lfloor s/4\rfloor$. We now have the number of non-singleton parts is $t^{*}\leq n/d\leq 4n/(s-3)<5/c^{*}$.

If $V_{i}\in P$ is not a singleton we have, as in Case (b), that

$$|S_{i}|\geq d-(2k-2)t^{*}\geq n(c^{*}/5-10c/c^{*})\geq n\left(6\sqrt{c}-\sqrt{c}/3\right)\geq 5\sqrt{c}n\;.$$

Consider now a singleton part $V_{i}$ and recall that if $V_{i}$ is of type $\alpha$, then $S_{i}$ is a star connecting $V_{i}$ only to singleton parts and $|S_{i}|=3d$. We again claim that there are no singletons of type $\beta$. Suppose that $V_{i}$ is of type $\beta$, i.e., at least $s-3d$ edges connect it to non-singleton parts. However, by Lemma 2.3 at most $(2k-2)t^{*}$ edges connect it to non-singleton parts, which is impossible since $(2k-2)t^{*}<n(10c/c^{*})<n(c^{*}/5)<d\leq s-3d$.

As in Case (b), since $|S_{i}|/8=\omega(\ln n)$, we may assume that $|T_{i}|\geq\frac{|S_{i}|}{4}$ holds for all $1\leq i\leq t$. Thus, we have that in the directed graph $D$, the out-degree of $i$ is

$$|T_{i}|\geq\frac{|S_{i}|}{4}\geq\frac{5}{4}\sqrt{c}n\geq 3c\log(1/c)n$$

where in the last inequality we have used that $c<1/900$. We therefore apply Lemma 2.4 to obtain $D^{\prime}$ with with $\kappa(U(D^{\prime}))\geq cn$ and where $d^{+}_{D^{\prime}}(i)\geq|T_{i}|-2c\log(1/c)n$ for all $i\in V(D^{\prime})$. The analogue of (2), which, recall, is only applied when $V_{i}$ is of type $\alpha$, now becomes

$$|T_{i}^{*}|=d^{+}_{D^{\prime}}(i)\geq|T_{i}|-2c\log(1/c)n\geq\frac{3d}{4}-n\sqrt{c}\geq\frac{3d}{4}-nc^{*}/30\geq\frac{3d}{4}-\frac{d}{4}\geq\frac{d}{2}$$

so, as in Case (a), $|V(B)|\geq d$, the new partition has fewer parts than $P$, and $B$ is $k$-connected, contradicting the minimality of $t$. ∎

3 Concluding remarks

As mentioned in the introduction, it is not difficult to prove that $f(2,n)=3$ for all $n\geq 5$ ($f(2,4)=2$) but as we have not found a proof in the literature, we present one.

Proposition 3.1.

$f(2,n)=3$ for all $n\geq 5$.

Proof.

The lower bound follows by considering a cycle of length $n$ when $n\geq 5$ is odd, and a cycle of length $n-1$ with an additional vertex connected to two non-adjacent cycle vertices when $n\geq 6$ is even. These graphs are $2$-connected and have no $2$-connected spanning bipartite subgraphs.

For the upper bound, suppose $G$ has $n$ vertices and is $3$-connected. Let $G^{*}$ be a subgraph of maximum order that is $2$-connected and bipartite. Notice that $G^{*}$ is nonempty since a $3$-connected graph has an even cycle. We claim that $|V(G^{*})|=n$. Assuming the contrary, let $A$ and $B$ denote the two parts of the bipartition of $G^{*}$ and let $G^{\prime}$ be the subgraph of $G$ induced by the vertices not in $G^{*}$. Note that it is possible that $G^{\prime}$ is not connected (nor bipartite), so let $X$ be the set of vertices of some connected component of $G^{\prime}$ and let $T$ be a spanning tree of $G[X]$. Let $C$ and $D$ denote the two parts of the bipartition of $T$.

Any vertex $x\in X$ cannot have two neighbors in $A$ as otherwise we can add to $G^{*}$ the vertex $x$ and two edges connecting it to $A$, forming a larger $2$-connected bipartite subgraph. Similarly, we cannot have two neighbors of $x$ in $B$. Thus, every $x\in X$ has at most one neighbor in $A$ and at most one neighbor in $B$. In particular, $X$ is not a singleton, as otherwise there is a vertex of degree $2$ (namely $x$) in $G$ which is impossible as $G$ is $3$-connected.

Suppose that $x$ has a neighbor $a\in A$ and a neighbor $b\in B$. We claim that (i) for any $y\in X$ with $y\neq x$ such that both $x$ and $y$ are in the same part of the bipartition of $T$ (either both in $C$ or both in $D$), $y$ cannot have any neighbor in $(A\cup B)\setminus\{a,b\}$. Indeed suppose $y$ has such a neighbor, say $a^{\prime}\in A$. Then we can add to $G^{*}$ the unique (even length) path of $T$ connecting $x$ and $y$, together with the edges $xa$ and $ya^{\prime}$, forming a larger $2$-connected bipartite subgraph. Similarly, we claim that (ii) for any $y\in X$ such that $x$ and $y$ are in opposite parts (one in $C$ and one in $D$), $y$ cannot have any neighbor in $(A\cup B)\setminus\{a,b\}$. Indeed suppose $y$ has such a neighbor, say $b^{\prime}\in B$. Then we can add to $G^{*}$ the unique (odd length) path of $T$ connecting $x$ and $y$, together with the edges $xa$ and $yb^{\prime}$, forming a larger $2$-connected bipartite subgraph.

We also claim (iii) that we cannot have a matching of size three between $X$ and $G^{*}$ (this is similar to the proof of Lemma 2.2). To see this, suppose that $x_{i}v_{i}$ for $i=1,2,3$ form a matching of size three between $X$ and $G^{*}$ where $v_{1},v_{2},v_{3}\in V(G^{*})$ and $x_{1},x_{2},x_{3}\in X$. If $v_{1},v_{2},v_{3}$ are in the same part of $G^{*}$ (either all in $A$ or all in $B$), then w.l.o.g. $x_{1}$ and $x_{2}$ are in the same part of $T$, so there is a path of even length in $T$ connecting $x_{1}$ and $x_{2}$, and we may add that path and the edges $x_{1}v_{1}$, $x_{2}v_{2}$ to $G^{*}$ and obtain a larger $2$-connected bipartite graph. Otherwise, assume $v_{1},v_{2}$ are in the same part of $G^{*}$ and $v_{3}$ is in the other part of $G^{*}$. If $x_{1}$ and $x_{2}$ are in the same part of $T$, then the same argument follows. Otherwise, $x_{1}$ and $x_{2}$ are in different parts of $T$. W.l.o.g. $x_{3}$ and $x_{2}$ are in distinct parts of $T$ and recall that $v_{2}$ and $v_{3}$ are in distinct parts of $G^{*}$. Then we can add the odd length path of $T$ between $x_{2}$ and $x_{3}$ and the edges $v_{2}x_{2}$, $v_{3}x_{3}$ to $G^{*}$ and obtain a larger $2$-connected bipartite graph.

Having shown (i)-(iii), we claim that we can disconnect $G$ by removing two vertices, which is a contradiction. Take a maximum matching $M$ between $X$ and $A\cup B$. If $M$ consists of one edge, we can disconnect $G$ by removing the endpoints of that single edge. Hence, by (iii), it consists of precisely two edges, say $M=\{xv_{1},yv_{2}\}$ where $x,y\in X$. If $v_{1}$ is the only neighbor of $X$ in $A\cup B$ and $v_{2}$ is the only neighbor of $y$ in $A\cup B$, then we can remove $v_{1},v_{2}$ from $G$ thereby separating $X$ from the rest of the graph (recall that $M$ is a maximum matching). Otherwise, w.l.o.g., $x$ has two neighbors in $A\cup B$, one of which is $v_{1}$ and the other denoted by $v_{3}$ (possibly $v_{3}=v_{2}$). If $y$ also has two neighbors in $A\cup B$, then by (i) and (ii) it must be that these neighbors are also $v_{1}$ and $v_{2}=v_{3}$. We can then remove $v_{1},v_{2}$ from $G$ and disconnect $X$. Otherwise, $v_{2}$ is the only neighbor of $y$ in $A\cup B$. Now, if $v_{2}=v_{3}$ we can delete $v_{1}$ and $v_{2}$ from $G$ thereby separating $X$ from the rest of the graph. Otherwise, we can delete $x$ and $v_{2}$ thereby separating $y$ from the rest of the graph. ∎

Recall that if $G$ is $2k-1$ edge-connected, then every maximum edge cut is $k$ edge-connected. It is easy to generalize this observation and show that if the edge connectivity of $G$ is larger than $r(k-1)/(r-1)$, then $G$ has a spanning $r$-chromatic subgraph that is $k$ edge-connected. Indeed, any maximum $r$-cut validates this fact. Stated otherwise, by allowing more colors for the spanning subgraph, we can keep the edge-connectivity close to its original value. The following proposition shows that the same holds for the case of $k$-connectivity in the linear regime.

Proposition 3.2.

Let $0<c<c^{\prime}<1$. There is a constant $r=r(c,c^{\prime})$ such that for all $n$ sufficiently large, if $G$ has $n$ vertices and is $\lfloor c^{\prime}n\rfloor$-connected, then $G$ has an $r$-colorable spanning subgraph that is $\lfloor cn\rfloor$-connected.

Proof.

Throughout the proof we assume that $cn$ and $c^{\prime}n$ are integers as this does not affect the correctness of the proposition. Let $t=c^{\prime}n$ and let $G$ be a $t$-connected graph on $n$ vertices. Let $r=r(c,c^{\prime})\geq 3$ be a constant whose existence is shown later. Consider an $r$-coloring of $V(G)$ where each vertex independently chooses its color uniformly at random. Let $G^{\prime}$ be the $r$-colorable spanning subgraph of $G$ consisting of all edges whose endpoints receive distinct colors. We will prove that with positive probability, $G^{\prime}$ is $cn$-connected.

By Menger’s Theorem, for any two distinct vertices $a,b\in V(G)$, there is a set ${\cal P}_{a,b}$ of $t-1$ paths connecting $a$ and $b$, each of length at least two, such that any two paths in ${\cal P}_{a,b}$ are internally vertex-disjoint. We say that a path $P\in{\cal P}_{a,b}$ survives if $P$ is present in $G^{\prime}$. It suffices to prove that the probability that fewer than $cn$ paths of ${\cal P}_{a,b}$ survive is less than $1/n^{2}$ as then, by the union bound and Menger’s theorem, $G^{\prime}$ is $cn$-connected with positive probability.

Fix two vertices $a$ and $b$ and fix a coloring of these two vertices (it is possible for $a$ and $b$ to have the same color). Consider some path $P\in{\cal P}_{a,b}$ and let $\ell=|E(P)|-1$ denote the number of its internal vertices. The number of possible colorings of these internal vertices is $r^{\ell}$ and at least $(r-1)^{\ell-1}(r-2)\geq(r-2)^{\ell}$ of these colorings yield a surviving path. Hence, the probability that $P$ survives is at least $(1-2/r)^{\ell}$. If $X_{P}$ denotes the indicator variable for survival and $X=\sum_{P\in{\cal P}_{a,b}}X_{P}$ is the number of surviving paths,

$${\mathbb{E}}[X]=\sum_{P\in{\cal P}_{a,b}}{\mathbb{E}}[X_{P}]\geq\sum_{P\in{\cal P}_{a,b}}\left(1-\frac{2}{r}\right)^{|E(P)|-1}\;.$$

The total number of internal vertices in all paths of $P\in{\cal P}_{a,b}$ is at most $n-2$, so the average number of internal vertices is at most $(n-2)/(t-1)$. By the last inequality and the AM-GM inequality we have

$${\mathbb{E}}[X]\geq(t-1)\left(1-\frac{2}{r}\right)^{(n-2)/(t-1)}\;.$$

Let $c^{*}=(c+c^{\prime})/2$. Recalling that $t=c^{\prime}n$ we have from the last inequality, that for all $r$ sufficiently large as a function of $c^{\prime}$ and $c^{*}$,

$${\mathbb{E}}[X]\geq c^{*}n\;.$$

Notice, however, that $X$ is the sum of $t-1$ independent indicator variables, as the paths are internally vertex-disjoint. Hence, by Chernoff’s inequality (in particular, Corollary A.1.7 of [1])

$$\Pr[X-{\mathbb{E}}[X]<(c-c^{*})n]<e^{-2(c^{*}-c)^{2}n^{2}/t}<\frac{1}{n^{2}}$$

implying that $\Pr[X<cn]<1/n^{2}$. As the last statement holds for any choice of the colors of $a$ and $b$, we have that the probability that the number of surviving paths in ${\cal P}_{a,b}$ (regardless of the colors of $a$ and $b$) is smaller than $cn$ is less than $1/n^{2}$. ∎