Packing spanning trees and spanning 2-connected k-edge-connected essentially $(2k-1)$-edge-connected subgraphs

Abstract

Let $k\ge 2, p\ge 1, q\ge 0$ be integers. We prove that every $(4kp-2p+2q)$-connected graph contains p spanning subgraphs $G_i$ for $1\le i\le p$ and q spanning trees such that all $p+q$ subgraphs are pairwise edge-disjoint and such that each $G_i$ is k-edge-connected, essentially $(2k-1)$-edge-connected, and $G_i -v$ is $(k-1)$-edge-connected for all $v\in V(G)$. This extends the well-known result of Nash-Williams and Tutte on packing spanning trees, a theorem that every 6p-connected graph contains p pairwise edge-disjoint spanning 2-connected subgraphs, and a theorem that every $(6p+2q)$-connected graph contains p spanning 2-connected subgraphs and q spanning trees, which are all pairwise edge-disjoint. As an application, we improve a result on k-arc-connected orientations.

1 Introduction

We consider undirected graphs without loops. Definitions and notations will be introduced in Sect. 2. In this paper, k, p, q denote nonnegative integers. A packing in a graph G means a set of pairwise edge-disjoint subgraphs of G.

The well-known theorem of Nash-Williams (1961) and Tutte (1961) on packing spanning trees implies Theorem 1.1.

Theorem 1.1

Every 2q-edge-connected graph contains a packing of q spanning trees.

Jordán (2005) extended Theorem 1.1 to edge-disjoint spanning 2-connected subgraphs, and Cheriyan et al. (2014) further generalized the result to a packing of spanning 2-connected subgraphs and spanning trees. For the definition of (k, l)-connectedness, please see Sect. 2.

Theorem 1.2

(Jordán 2005). Every 6p-connected graph contains a packing of p spanning 2-connected subgraphs.

Theorem 1.3

(Cheriyan et al. 2014). Let $p\ge 1$ and $q\ge 0$. Every $(6p +2q, 2p)$-connected simple graph contains a packing of p spanning 2-connected subgraphs and q spanning trees.

Actually Theorems 1.2 and 1.3 are corollaries of stronger results in Jordán (2005) and Cheriyan et al. (2014), see Corollaries 4.3 and 4.4.

In this paper, we prove the following result.

Theorem 1.4

Let $k\ge 2$, $p\ge 1$, $q\ge 0$. For every $(4kp-2p+2q, kp)$-connected simple graph G and $Y\subset E(G)$ with $|Y|\le (2k-1)p+q$, $G-Y$ contains a packing of p spanning subgraphs $G_i$ for $1\le i\le p$ and q spanning trees such that

• (i) Each $G_i$ is 2-connected, k-edge-connected and essentially $(2k-1)$-edge-connected.

• (ii) For each $G_i$ and each vertex $v\in V(G)$, $G_i -v$ is $(k-1)$-edge-connected.

As an application, we investigate k-arc-connected orientations of graphs. Király and Szigeti proved the following characterization for Eulerian graphs (Theorem 1.5). By using Theorems 1.3 and 1.5, Cheriyan et al. (2014) provided a sufficient connectivity condition for the existence of k-arc-connected orientations, see Theorem 1.6.

Theorem 1.5

(Király and Szigeti 2006). An Eulerian graph G has an orientation D such that $D-v$ is k-arc-connected for all $v\in V(G)$ if and only if $G-v$ is 2k-edge-connected for all $v\in V(G)$.

Theorem 1.6

(Cheriyan et al. 2014). Every $(12k+2, 4k)$-connected simple graph G has an orientation D such that $D-v$ is k-arc-connected for all $v\in V(G)$.

By similar argument to that of Cheriyan et al. (2014), we improve Theorem 1.6 as below.

Theorem 1.7

Every $(8k+4, 2k+1)$-connected simple graph G has an orientation D such that $D-v$ is k-arc-connected for all $v\in V(G)$.

Proof

By Theorem 1.5, it suffices to show that G contains an Eulerian spanning subgraph H such that $H-v$ is 2k-edge-connected for all $v\in V(G)$. Since G is $(8k+4, 2k+1)$-connected, by Theorem 1.4, G contains a spanning subgraph R and a spanning tree S such that $R-v$ is 2k-edge-connected for all $v\in V(G)$ and R, S are edge-disjoint. Let T be the set of all vertices of odd degree in R and so |T| is even. Since S is spanning, it contains a T-join, denoted by F. Let H be the graph with vertex set V(G) and edge set $E(R)\cup F$. Then H is an Eulerian spanning subgraph of G such that $H-v$ is 2k-edge-connected for all $v\in V(G)$, completing the proof. $\square$

Theorem 1.7 is also related to a conjecture of Thomassen (1989). Thomassen (1989) conjectures that, for every positive integer k, there exists a (smallest) g(k) such that every g(k)-connected graph has a k-connected orientation. Jordán (2005) shows that $g(2)\le 18$, while Theorem 1.6 implies that $g(2)\le 14$. It is not hard to see $g(2)\le 12$ from Theorem 1.7. Recently, Thomassen (2015) shows that $g(2)=4$.

In Sect. 4, we will prove a stronger theorem, Theorem 4.1, which is the main result. Theorem 1.4 is a corollary of Theorem 4.1. The proof of Theorem 4.1 uses a matroidal method. We must point out that the proof technique is similar to that in Cheriyan et al. (2014). In Sect. 3, we will introduce k-rigid graphs and k-rigidity matroids.

2 Definitions

Let $G=(V,E)$ be a graph. For any edge subset $F\subseteq E(G)$, G[F] is the subgraph of G induced by F, while G(F) denotes the spanning subgraph of G with vertex set V(G) and edge set F. For any vertex subset $X\subseteq V(G)$, G[X] denotes the subgraph of G induced by X.

For any $X\subseteq V(G)$ and $F\subseteq E(G)$, $E_F(X)$ and $i_F(X)$ denote the set and the number of edges of F in G[X], respectively. If $F=E(G)$, then usually we use $E_G(X)$ and $i_G(X)$ for $E_F(X)$ and $i_F(X)$, respectively.

For any nonempty proper subset $X\subset V(G)$, let $d_G(X)$ denote the number of edges between X and $V(G)-X$. A graph G is k -edge-connected if $d_G(X)\ge k$ for every nonempty proper subset $X\subset V(G)$. A graph G is essentially k -edge-connected if $d_G(X)\ge k$ for every $X\subset V(G)$ with $2\le |X|\le |V(G)|-2$.

For positive integers k and l, G is ( k ,  l )-connected if $|V(G)|> k/l$ and $G-X$ is $(k-l|X|)$-edge-connected for every $X\subset V(G)$. For instance, a graph G is (3k, k)-connected if G is 3k-edge-connected, $G-v$ is 2k-edge-connected for any vertex $v\in V(G)$ and $G-\{u,v\}$ is k-edge-connected for any two vertices $u,v\in V(G)$. By definition, k-edge-connectedness is equivalent to (k, k)-connectedness.

Remark 1

(See also Cheriyan et al. 2014). Every k-connected graph contains a (k, 1)-connected simple spanning subgraph, and (k, 1)-connectedness implies (k, l)-connectedness for $l\ge 1$.

Let $T\subseteq V(G)$. A subset $F\subseteq E(G)$ is a T -join if the set of all odd vertices of G[F] is equal to T. A connected graph has a T-join if and only if |T| is even.

A digraph $D=(V, A)$ is strongly connected if for any two vertices $u,v\in V(D)$, there is a directed path from u to v in D. A digraph D is k -arc-connected if $D-F$ is strongly connected for all $F\subseteq A(D)$ with $|F|\le k-1$. A digraph D is k -connected if $|V|\ge k$ and $D-X$ is strongly connected for all $X\subset V(D)$ with $|X|\le k-1$.

3 k-rigid graphs and k-rigidity matroids

Let $k\ge 1$ and $G=(V,E)$ be a graph. A subset $S\subseteq E$ is k -sparse if $i_S(X)\le k|X|-2k+1$ for all $X\subseteq V$ with $|X|\ge 2$. This was originally defined in Jackson and Jordán (2005). By definition, the empty set and any set that consists of a single edge are k-sparse. A graph G is k -sparse if E(G) is a k-sparse set. If in addition $|E(G)|=k|V(G)|-2k+1$, then G is minimally k -rigid. A graph G is k -rigid if G contains a spanning minimally k-rigid subgraph. By definition, 1-sparse graphs, minimally 1-rigid graphs and 1-rigid graphs are equivalent to forests, trees and connected graphs, respectively. A 2-rigid graph is usually called a rigid graph.

Proposition 3.1

Each of the following statements holds.

• (i) Any k-sparse graph is simple.

• (ii) For any nontrivial k-rigid graph G, $|V(G)|\ge 2k-1$ or $|V(G)|=2$.

• (iii) Any k-rigid graph G with $|V(G)|\ge 2k-1$ is k-edge-connected and essentially $(2k-1)$-edge-connected.

• (iv) Let $k\ge 2$ and G be a k-rigid graph with $|V(G)|\ge 2k-1$. For any vertex $v\in V(G)$, $G-v$ is $(k-1)$-edge-connected, and thus G is 2-connected.

Proof

• (i) By definition, for every subset $X\subseteq V(G)$ with $|X|=2$ of a k-sparse graph G, $|i_G (X)|\le 2k-2k+1=1$. Thus G is simple.

• (ii) Let $|V(G)|=n$. Since G is k-rigid, G contains a minimally k-rigid spanning subgraph $G'$. By (i), $G'$ is simple, and thus $\frac{n(n-1)}{2}\ge |E(G')| = kn-2k+1$. Then $n^2 -(2k+1)n +4k-2\ge 0$, which implies that $n\ge 2k-1$ or $n\le 2$.

• (iii) Without loss of generality, we may assume that G is minimally k-rigid. We show that G is essentially $(2k-1)$-edge-connected by way of contradiction. Assume that there exists an edge subset $Y\subset E(G)$ with $|Y|\le 2k-2$ such that $G-Y$ has 2 components $G_1$ and $G_2$ with $|V(G_i)|\ge 2$ for $i=1,2$. As G is minimally k-rigid, $|E(G_i)|\le k|V(G_i)| -2k +1$. Thus $|E(G)|=|E(G_1)|+ |E(G_2)| +|Y| \le (k|V(G_1)| -2k +1) + (k|V(G_2)| -2k +1) + (2k-2) =k|V(G)|-2k$, contradicting that G is minimally k-rigid. This proves that G is essentially $(2k-1)$-edge-connected. If G is not k-edge-connected, then there exists an edge subset $Y\subset E(G)$ with $|Y|\le k-1$ such that $G-Y$ has 2 components $G_1$ and $G_2$, one of which, say $G_2$, consists of a single vertex. Thus $|E(G)|=|E(G_1)| +|Y| \le (k|V(G_1)| -2k +1) + (k-1) =k|V(G)| -2k$, contradicting that G is minimally k-rigid. Thus G is k-edge-connected.

• (iv) Without loss of generality, we may assume that G is minimally k-rigid. Towards a proof by contradiction, we assume that for a vertex $v\in V(G)$, there exists an edge subset $Y\subset E(G-v)$ with $|Y|\le k-2$ such that $(G-v)-Y$ has 2 components $H_1$ and $H_2$. Let $G_i =G[V(H_i)\cup \{v\}]$ for $i=1,2$. Then $|V(G_i)|\ge 2$, and so $|E(G_i)|\le k|V(G_i)| -2k +1$. Thus $|E(G)|=|E(G_1)|+ |E(G_2)| +|Y| \le (k|V(G_1)| -2k +1) + (k|V(G_2)| -2k +1) + (k-2) =k(|V(G_1)|+|V(G_2)|)-3k =k|V(G)|-2k$, contradicting that G is minimally k-rigid. Thus $G-v$ is $(k-1)$-edge-connected. In particular, since $k\ge 2$, $G-v$ is connected for every $v\in V(G)$, and thus G is 2-connected.

$\square$

Let $\mathscr {S}_k$ be the collections of all k-sparse sets. One can verify that the collection $\mathscr {S}_k$ forms the set of independent sets of a matroid. Actually, this matroid $(E, \mathscr {S}_k)$ is a special case of the count matroid (See page 453 of Frank 2011). In this paper, the matroid $(E, \mathscr {S}_k)$ is called the k -rigidity matroid of G, denoted by $\mathcal {R}_k(G)$. By definition, $\mathcal {R}_1(G)$ is the circuit matroid $\mathcal {C}(G)$ of G and $\mathcal {R}_2(G)$ is the rigid matroid $\mathcal {R}(G)$ of G (see Lovász and Yemini 1982 for more about $\mathcal {R}(G)$).

The rank function of $\mathcal {R}_2(G)$ is given by Lovász and Yemini (1982). While the rank of $\mathcal {R}_k(G)$ can be seen in Jackson and Jordán (2005), the complete rank function of $\mathcal {R}_k(G)$ is not given. We present the rank function of $\mathcal {R}_k(G)$ in the following proposition.

Proposition 3.2

Let $k\ge 2$. Given $F\subseteq E$, the rank function of $\mathcal {R}_k(G)$ is

$$\begin{aligned} r_k(F)=\min \left\{ \sum _{X\in \mathcal {X}} (k|X|-2k+1) \right\} , \end{aligned}$$

(1)

where the minimum is taken over all collections $\mathcal X$ of subsets V(G) such that $|X|\ge 2$ for all $X\in \mathcal {X}$ and such that $\{E_F(X)| X\in \mathcal {X}\}$ partitions F.

Proof

Let $F'\subseteq F$ be a maximal k-sparse set. It suffices to show $|F'|=\min \{\sum _{X\in \mathcal {X}} (k|X|-2k+1)\}$. As $F'$ is k-sparse, $|F'\cap E_{F'}(X)|\le k|X|-2k+1$ for every $X\in \mathcal {X}$. Thus $|F'|\le \sum _{X\in \mathcal {X}} (k|X|-2k+1)$ for any collection $\mathcal {X}$. Now we show that there exists a collection $\mathcal {X}_0$ such that $|F'| = \sum _{X\in \mathcal {X}_0} (k|X|-2k+1)$.

Since each single edge of $F'$ is induced by a vertex subset X with $i_{F'}(X)=k|X|-2k+1$ (actually $|X|=2$), there are some maximal vertex subsets X with $i_{F'}(X)=k|X|-2k+1$. Let $X_1,X_2,\cdots , X_t\subseteq V(G[F'])$ be maximal vertex subsets such that $i_{F'}(X_i)=k|X_i|-2k+1$ for $1\le i\le t$. Let $\mathcal {X}_0=\{X_1,X_2,\cdots , X_t\}$.

Claim 1

$|X_i\cap X_j|\le 1$ for $1\le i\ne j\le t$.

If not, then $|X_i\cap X_j|\ge 2$ for some $i\ne j$. We will show it then follows that $i_{F'}(X_i\cup X_j) =k|X_i\cup X_j| -2k+1$. Actually $i_{F'}(X_i\cup X_j) + i_{F'}(X_i\cap X_j)\ge i_{F'}(X_i) + i_{F'}(X_j)$, which implies that

$$\begin{aligned} i_{F'}(X_i\cup X_j)\ge & {} i_{F'}(X_i) + i_{F'}(X_j) - i_{F'}(X_i\cap X_j)\\\ge & {} (k|X_i|-2k+1) + (k|X_j|-2k+1) - (k|X_i\cap X_j|-2k+1)\\= & {} k(|X_i|+|X_j|-|X_i\cap X_j|)-2k+1\\= & {} k|X_i\cup X_j| -2k+1. \end{aligned}$$

As $F'$ is k-sparse, $i_{F'}(X_i\cup X_j)\le k|X_i\cup X_j| -2k+1$, and thus $i_{F'}(X_i\cup X_j) =k|X_i\cup X_j| -2k+1$, which is contrary to the maximality of $X_i$ and $X_j$. This completes the proof of the claim.

Notice that each single edge of $F'$ is induced by a vertex subset X with $i_{F'}(X)=k|X|-2k+1$ (actually $|X|=2$), then each edge of $F'$ is covered by a maximal vertex subset $X_j$ for some $j=1,2,\cdots , t$. By Claim 1, $\{E_{F'}(X_1), E_{F'}(X_2),\cdots , E_{F'}(X_t)\}$ is a partition of $F'$. Thus $|F'|=\sum _{1\le j\le t} i_{F'}(X_j)= \sum _{1\le j\le t} (k|X_j|-2k+1)$.

It remains to prove $\{E_F(X)| X\in \mathcal {X}_0\}$ partitions F. Let $e\in F$. If $e\in F'$, then we are done. Thus we may assume that $e\in F-F'$. As $F'$ is a maximal k-sparse set, $F'\cup \{e\}$ is not k-sparse. Then there exists $X\subseteq V(G)$ such that $i_{F'\cup \{e\}}(X)\ge k|X|-2k+2$. Furthermore, $e\in E_{F'\cup \{e\}}(X)$, which implies that $i_{F'}(X)= k|X|-2k+1$. Then X is included in some maximal set $X_j$ for $1\le j\le t$. Hence $e\in E_{F}(X_j)$, completing the proof. $\square$

Remark 2

By the definition of k-rigid graphs, the proof of Proposition 3.2 shows that, there is a collection $\mathcal X$ to realize the minimum of the right side of (1) such that each $X\in \mathcal X$ induces a k-rigid subgraph of G[F].

Remark 3

The rank of $\mathcal {R}_k(G)$, $r_k(E)\le k|V(G)|-2k+1$. A graph G is k-rigid if and only if the rank of $\mathcal {R}_k(G)$ is $k|V(G)|-2k+1$.

Proof of Remark 3

By definition, a spanning k-sparse subgraph of G has at most $k|V(G)|-2k+1$ edges. This is the maximum cardinality of an independent set of $\mathcal {R}_k(G)$, and thus $r_k(E)\le k|V(G)|-2k+1$. If G is k-rigid, then G has a spanning k-sparse subgraph with exact $k|V(G)|-2k+1$ edges. This is the maximum cardinality of an independent set of $\mathcal {R}_k(G)$. Thus the cardinality of any base of $\mathcal {R}_k(G)$ is $k|V(G)|-2k+1$, which implies the rank of $\mathcal {R}_k(G)$ is $k|V(G)|-2k+1$. Inversely, if the rank of $\mathcal {R}_k(G)$ is $k|V(G)|-2k+1$, then G has a spanning k-sparse subgraph H with exact $k|V(G)|-2k+1$ edges. By definition, H is a spanning minimally k-rigid subgraph of G, and thus G is k-rigid. $\square$

Corollary 3.3

Let $\mathcal X$ be a collection that realizes the minimum of the right side of (1) defined in Proposition 3.2, and $\mathcal Y\subseteq \mathcal X$. Then $r_k \left( \cup _{X\in \mathcal {Y}} E_F(X)\right) = \sum _{X\in \mathcal {Y}} (k|X|-2k+1)$.

Proof

Since $\mathcal X$ is a collection that realizes the minimum of the right side of (1), $r_k(F)=\sum _{X\in \mathcal {X}} (k|X|-2k+1)$. Also $F= \cup _{X\in \mathcal {X}} E_F(X) = \left( \cup _{X\in \mathcal {Y}} E_F(X) \right) \cup \left( \cup _{X\in \mathcal {X-Y}} E_F(X) \right)$. By (1), $r_k(\cup _{X\in \mathcal {Y}} E_F(X))\le \sum _{X\in \mathcal {Y}} (k|X|-2k+1)$ and $r_k(\cup _{X\in \mathcal {X-Y}} E_F(X))\le \sum _{X\in \mathcal {X-Y}} (k|X|-2k+1)$. By submodularity of rank function,

$$\begin{aligned} \sum _{X\in \mathcal {X}} (k|X|-2k+1)= & {} r_k(F) \\\le & {} r_k(\cup _{X\in \mathcal {Y}} E_F(X)) + r_k(\cup _{X\in \mathcal {X-Y}} E_F(X))\\\le & {} \sum _{X\in \mathcal {Y}} (k|X|-2k+1) + \sum _{X\in \mathcal {X-Y}} (k|X|-2k+1)\\= & {} \sum _{X\in \mathcal {X}} (k|X|-2k+1). \end{aligned}$$

Thus every equality holds above. In particular, $r_k \left( \cup _{X\in \mathcal {Y}} E_F(X)\right) = \sum _{X\in \mathcal {Y}} (k|X|-2k+1)$. $\square$

Suppose that $G=(V,E)$ is a graph with $|V(G)|=n$. Let $\mathcal {F}$ be the collection of all edge subsets each of which induces a forest. Then $\mathcal {F}$ forms all independent sets of a matroid $(E,\mathcal {F})$ on ground set E, which is the circuit matroid $\mathcal {M}(G)$ of G. The rank function of $\mathcal {M}(G)$ is given by $r_{\mathcal M}(F) = n - c(F)$, where c(F) denotes the number of components of G(F).

Let $\mathcal {N}_{k,p,q}(G)$ be the matroid on ground set E obtained by taking matroid union of p copies of the k-rigidity matroid $\mathcal {R}_k(G)$ and q copies of the circuit matroid $\mathcal {M}(G)$. By a theorem of Edmonds on the rank of matroid union Edmonds (1968), the rank of $\mathcal {N}_{k,p,q}(G)$ is

$$\begin{aligned} r_{k,p,q}(E)=\min _{F\subseteq E} \left\{ p r_k(F) + q r_{\mathcal M}(F) + |E-F| \right\} . \end{aligned}$$

(2)

Thus $r_{k,p,q}(E)\le p r_k(E) + q r_{\mathcal M}(E)= p(kn-2k+1) + q(n-1)$.

4 Packing k-rigid spanning subgraphs

In this section, we prove Theorem 1.4 by providing a stronger result (Theorem 4.1). In Theorem 4.1, we present a connectivity condition for packing spanning k-rigid subgraphs and spanning trees. Theorem 1.4 then follows from Proposition 3.1 and Theorem 4.1.

Theorem 4.1

Let $k\ge 2, p\ge 1, q\ge 0$. For a $(4kp-2p+2q, kp)$-connected simple graph G and $Y\subset E(G)$ with $|Y|\le (2k-1)p+q$, $G-Y$ contains a packing of p spanning k-rigid subgraphs and q spanning trees.

The theorem also implies the following known results.

Corollary 4.2

(Lovász and Yemini 1982). Every 6-connected graph is 2-rigid.

Corollary 4.3

(Jordán 2005). Every 6p-connected graph contains a packing of p spanning 2-rigid subgraphs.

Corollary 4.4

(Cheriyan et al. 2014). Every $(6p +2q, 2p)$-connected simple graph contains a packing of p spanning 2-rigid subgraphs and q spanning trees.

In the rest of this section, we prove Theorem 4.1.

Proof of Theorem 4.1

Let $G'=G-Y$ and $E=E(G')=E(G)-Y$. It suffices to show that the rank of $\mathcal {N}_{k,p,q}(G')$ is

$$\begin{aligned} r_{k,p,q}(E) = p(kn-2k+1) + q(n-1). \end{aligned}$$

Choose $F\subseteq E$ to be a set with smallest size that minimizes the right side of (2), then

$$\begin{aligned} r_{k,p,q}(E)= pr_k(F) + qr_{\mathcal M}(F) + |E-F|. \end{aligned}$$

(3)

By (1) and Remark 2, there exists a collection $\mathcal {X}$ of subsets V such that $\{E_F(X)| X\in \mathcal {X}\}$ partitions F and

$$\begin{aligned} r_k(F)=\sum _{X\in \mathcal {X}} (k|X|-2k+1), \end{aligned}$$

(4)

and such that each $X\in \mathcal X$ induces a k-rigid subgraph.

Claim 2

For each $X\in \mathcal {X}$, $|X|\ge 2k-1$.

Proof of Claim 2

Since each $X\in \mathcal {X}$ induces a k-rigid subgraph, by Proposition 3.1, $|X|\ge 2k-1$ or $|X|=2$. Thus it suffices to show that $|X|\ne 2$ for any $X\in \mathcal {X}$. If not, then let $\mathcal {X}'$ denote the collection of $X\in \mathcal {X}$ with $|X|=2$. Then $r_k(F)=\sum _{X\in \mathcal {X-X'}} (k|X|-2k+1)+\sum _{X\in \mathcal {X'}} (k|X|-2k+1) =\sum _{X\in \mathcal {X-X'}} (k|X|-2k+1)+|\mathcal {X'}|$. Let $H\subset F$ be the set of edges obtained by deleting all edges induced by each X with $|X|=2$. Then $\mathcal {X-X'}$ is a collection of subsets of V that partition H. By (1), $r_k(H)\le \sum _{X\in \mathcal {X-X'}} (k|X|-2k+1)$. As $G'$ is simple, $|F-H|\le |\mathcal {X'}|$. Since $H\subset F$, we have $r_{\mathcal M}(H)\le r_{\mathcal M}(F)$. Thus

$$\begin{aligned}&pr_k(H) + qr_{\mathcal M}(H) + |E-H|\\&\quad \le p\sum _{X\in \mathcal {X-X'}}(k|X|-2k+1)+ qr_{\mathcal M}(F) + |E-F| + |F-H| \\&\quad \le p\sum _{X\in \mathcal {X-X'}}(k|X|-2k+1)+ qr_{\mathcal M}(F) + |E-F| + |\mathcal {X'}| \\&\quad \le pr_k(F) + qr_{\mathcal M}(F) + |E-F|, \end{aligned}$$

contrary to the minimality of F. This completes the proof of the claim. $\square$

Claim 3

For every $\mathcal {Y}\subseteq \mathcal {X}$, there is a vertex that is contained in a single element of $\mathcal {Y}$.

Proof of Claim 3

If not, then every vertex is contained in at least two elements of $\mathcal {Y}$. Let $n_\mathcal {Y}$ be the number of vertices in all elements of $\mathcal {Y}$. Then $\sum _{X\in \mathcal {Y}}|X|\ge 2 n_\mathcal {Y}$. By Remark 3, Corollary 3.3 and Claim 2, we have

$$\begin{aligned} k n_\mathcal {Y} -2k+1\ge & {} r_k \left( \cup _{X\in \mathcal {Y}} E_F(X)\right) = \sum _{X\in \mathcal {Y}} (k|X|-2k+1)\\= & {} \sum _{X\in \mathcal {Y}}((k-1)|X|) + \sum _{X\in \mathcal {Y}} (|X|-2k+1)\\\ge & {} 2(k-1) n_\mathcal {Y} +0\\\ge & {} k n_\mathcal {Y}, \end{aligned}$$

a contradiction. This proves the claim. $\square$

Let $|V(G'[F])|=n_1$ and $n_2=n-n_1$. Then there are $n_2$ isolated vertices in $G'(F)$. For each $X\in \mathcal {X}$, define $X_B = X\cap (\cup _{X\ne Y\in \mathcal {X}}Y)$ and $X_I=X-X_B$. Let $\mathcal {I_X}=\{X\in \mathcal {X}: X_I\ne \emptyset \}$. We will show that

$$\begin{aligned} c(F)\le |\mathcal {I_X}| + n_2. \end{aligned}$$

(5)

Proof of (5). Let $H'$ be any connected component of $G'(F)$ that is not an isolated vertex. This $H'$ is called a nontrivial component. By Remark 2, each $X\in \mathcal {X}$ induces a connected subgraph of $G'(F)$ and thus $H'$ actually is a sugraph of $G'(F)$ induced by some elements X’s of $\mathcal {X}$. Let $\mathcal {Y}$ be the collection of these X’s, and thus $\mathcal {Y}\subseteq \mathcal {X}$. By Claim 3, there is a vertex v in $V(H')$ that is contained in a single element of $\mathcal {Y}$. By definition, $v\in X_I$ and thus $X_I\ne \emptyset$. This shows that every nontrivial component of $G'(F)$ contains an X such that $X_I\ne \emptyset$. Hence $G'(F)$ contains at most $|\mathcal {I_X}|$ components that are not isolated vertices, which implies that $c(F)\le |\mathcal {I_X}| + n_2$.

Since $\mathcal {X}$ covers F and thus contains all vertices of $G'[F]$, each vertex of $X_B$ lies in at least two different $X\in \mathcal {X}$ and each $X_I$ is contained in a single X, we have $\sum _{X\in \mathcal {X}}|X_B| + 2\sum _{X\in \mathcal {I_X}}|X_I|\ge 2n_1$, which implies

$$\begin{aligned} \sum _{X\in \mathcal {X}}|X| + \sum _{X\in \mathcal {I_X}}|X_I|\ge 2n_1. \end{aligned}$$

(6)

Now we will use the connectivity condition of G to show a lower bound on $|E-F|$. Let $v_1,v_2,\cdots ,v_{n_2}$ be isolated vertices of G(F). Since G is $(4kp-2p+2q, kp)$-connected, $d_{G-X_B}(X_I)\ge 4kp-2p+2q - kp|X_B|$ for each $X\in \mathcal {X}$ and $d_G(v_i)\ge 4kp-2p+2q$ for $1\le i\le n_2$. For every $X\in \mathcal {X}$, no edge of F contributes to $d_{G-X_B}(X_I)$. For $1\le i\le n_2$, no edge of F contributes to $d_G(v_i)$. Thus

$$\begin{aligned} |E-F|\ge & {} |E(G)-Y-F| = |E(G)-F| -|Y| \nonumber \\\ge & {} \frac{1}{2}\left( \sum _{X\in \mathcal {I_X}} d_{G-X_B}(X_I) +\sum _{i=1}^{n_2} d_{G}(v_i)\right) -((2k-1)p+q) \nonumber \\\ge & {} \frac{1}{2}\left( \sum _{X\in \mathcal {I_X}}(4kp-2p+2q - kp|X_B|) + n_2 (4kp-2p+2q)\right) \nonumber \\&\quad -(2k-1)p-q \nonumber \\= & {} p\sum _{X\in \mathcal {I_X}}(2k-1-\frac{k}{2}|X_B|) +p(2k-1)(n_2 -1) \nonumber \\&\quad + q(|\mathcal {I_X}| +n_2 -1) \end{aligned}$$

(7)

By Claim 2, $\frac{k}{2}|X|-2k+1 \ge 0$. As $\mathcal {I_X}\subseteq \mathcal {X}$, we have

$$\begin{aligned} \sum _{X\in \mathcal {X}} \left( \frac{k}{2}|X|-2k+1\right) \ge \sum _{X\in \mathcal {I_X}} \left( \frac{k}{2}|X|-2k+1\right) . \end{aligned}$$

(8)

By (3), (4), (5), (6), (7) and (8),

$$\begin{aligned} r_{k,p,q}(E)= & {} p\sum _{X\in \mathcal {X}} (k|X|-2k+1) + qr_{\mathcal M}(F) + |E-F|\\= & {} p\left( \sum _{X\in \mathcal {X}}\frac{k}{2}|X| + \sum _{X\in \mathcal {X}} (\frac{k}{2}|X|-2k+1)\right) + q(n-c(F)) + |E-F|\\\ge & {} p\left( \sum _{X\in \mathcal {X}}\frac{k}{2}|X| + \sum _{X\in \mathcal {I_X}} (\frac{k}{2}|X|-2k+1)\right) + q(n-c(F))\\&+ p\sum _{X\in \mathcal {I_X}}(2k-1-\frac{k}{2}|X_B|)+p(2k-1)(n_2 -1) +q(|\mathcal {I_X}| +n_2 -1)\\= & {} p\left( \sum _{X\in \mathcal {X}}\frac{k}{2}|X| +\sum _{X\in \mathcal {I_X}}\frac{k}{2}|X_I| +(2k-1)n_2\right) \\&\quad -p(2k-1) +q(n-c(F)+ |\mathcal {I_X}| +n_2 -1)\\\ge & {} \frac{pk}{2}(2n_1 + 2n_2) -p(2k-1) + q(n-1) + q(|\mathcal {I_X}| + n_2 -c(F))\\\ge & {} p(kn-2k+1) + q(n-1). \end{aligned}$$

As $r_{k,p,q}(E)\le p(kn-2k+1) +q(n-1)$, it turns out that $r_{k,p,q}(E)= p(kn-2k+1) +q(n-1)$. $\square$