Enomoto and Ota’s Conjecture Holds for Large Graphs

Abstract

In 2000, Enomoto and Ota conjectured that if a graph G satisfies $\sigma _{2}(G) \ge |G| + k - 1$, then for any set of k vertices $v_{1}, \ldots , v_{k}$ and for any positive integers $n_{1}, \ldots , n_{k}$ with $\sum n_{i} = |G|$, there exists a partition of V(G) into k paths $P_{1}, \ldots , P_{k}$ such that $v_{i}$ is an end of $P_{i}$ and $|P_{i}| = n_{i}$ for all i. We prove this conjecture when |G| is large. Our proof uses the Regularity Lemma along with several extremal lemmas, concluding with an absorbing argument to retrieve misbehaving vertices.

1 Introduction

For all basic definitions and notation, see [2]. Let $\sigma _2(G)$ denote the minimum sum of degrees of two nonadjacent vertices in the graph G. In 2000, Enomoto and Ota conjectured the following and proved several cases.

Conjecture 1

(Enomoto and Ota [5]) Given an integer $k \ge 3$, let G be a graph of order n and let $n_{1}, n_{2}, \dots , n_{k}$ be a set of k positive integers with $\sum n_{i} = n$. If $\sigma _{2}(G) \ge n + k - 1$, then for any k distinct vertices $x_{1}, x_{2}, \dots , x_{k}$ in G, there exists a set of vertex-disjoint paths $P_{1}, P_{2}, \dots , P_{k}$ such that for all i with $1\le i \le k$, we have $|P_{i}| = n_{i}$ and $x_i$ is an endpoint of $P_{i}$.

This conjecture would certainly be sharp by the following construction. Let $G'$ be a complete graph on $n - 1$ vertices. Let S be a set of k vertices in $G'$ and let G be constructed by adding a new vertex to $G'$ which is adjacent to each of the vertices in S. This graph has $\sigma _{2}(G) = n + k - 2$ but if S is the selected set of vertices and all of the paths must have length at least 2, the paths cannot be constructed as desired. Note that there is no published general minimum degree version of Conjecture 1, but the main result of this paper implies a minimum degree version for large graphs.

A partial solution to Conjecture 1 was provided by Magnant and Martin in the sense that the path lengths could only be prescribed within a small fraction of n.

Theorem 1

(Magnant and Martin [11]) Given an integer $k \ge 3$, for every set of k positive real numbers $\eta _{1}, \dots \eta _{k}$ with $\sum _{i = 1}^{k} \eta _{i} = 1$, and for every $\epsilon > 0$, there exists $n_{0}$ such that for every graph G of order $n \ge n_{0}$ with $\sigma _{2}(G) \ge n + k - 1$ and for every choice of k vertices $S = \{ x_{1}, \dots , x_{k} \} \subseteq V(G)$, there exists a set of vertex-disjoint paths $P_{1}, \dots , P_{k}$ which span V(G) with $P_{i}$ beginning at the vertex $x_{i}$ and $(\eta _{i} - \epsilon )n< |P_{i}| < (\eta _{i} + \epsilon )n$. Also, the condition on $\sigma _{2}(G)$ is sharp.

The following result, the main goal of this work, shows that Conjecture 1 holds when n is sufficiently large relative to k.

Theorem 2

Given an integer $k \ge 3$, let G be a graph of sufficiently large order $n = n(k)$ and let $n_{1}, n_{2}, \dots , n_{k}$ be a set of k positive integers with $\sum n_{i} = n$. If $\sigma _{2}(G) \ge n + k - 1$, then for any k distinct vertices $x_{1}, x_{2}, \dots , x_{k}$ in G, there exists a set of vertex-disjoint paths $P_{1}, P_{2}, \dots , P_{k}$ such that for all i with $1 \le i \le k$, we have $|P_{i}| = n_{i}$ and $x_{i}$ is an endpoint of $P_{i}$.

Our proof utilizes several extremal lemmas based on the structure of the reduced graph provided by the Regularity Lemma. Our lemmas deal with the cases where the minimum degree is small, where the reduced graph has a large independent set, and where the connectivity of the reduced graph is small.

2 Preliminaries

Much of this section comes from [6] but is included here for completeness.

Given two sets of vertices A and B, let E(A, B) denote set of edges with one end in A and one end in B and let $e(A, B) = |E(A, B)|$ be the number of such edges. Define the density between A and B to be

$$\begin{aligned} d(A, B) = \frac{e(A, B)}{|A||B|}. \end{aligned}$$

Let $\epsilon > 0$. Given a graph G and two nonempty disjoint vertex sets $A, B \subset V$, we say that the pair (A, B) is $\epsilon$-regular if for every $X \subset A$ and $Y \subset B$ satisfying

$$\begin{aligned} |X|> \epsilon |A| ~ ~ ~ \text {and} ~ ~ ~ |Y| > \epsilon |B| \end{aligned}$$

we have

$$\begin{aligned} |d(X, Y) - d(A, B)| < \epsilon . \end{aligned}$$

If a pair of vertex sets is $\epsilon$-regular, then by the Slicing Lemma, every reasonably-sized subpair is at worst $2\epsilon$-regular.

Fact 1

(Slicing Lemma [9], Fact 1.3) Let (A, B) be an $\epsilon$-regular pair with density $d$, and, for $\alpha > \epsilon$, let $A' \subseteq A$, $|A'| \ge \alpha |A|$, $B'\subseteq B$ and $|B'| \ge \alpha |B|$. Then $(A',B')$ is an $\epsilon '$-regular pair with $\epsilon ' = \max \{\epsilon /\alpha ,2\epsilon \}$, and for its density $d'$, we have $|d'-d|<\epsilon$.

Despite its seemingly basic nature, Fact 1 plays an important role in the proof of our main result. We will frequently be stripping $\epsilon$-regular pairs of small numbers of vertices—Fact 1 guarantees that these smaller pairs retain similar levels of uniformity and density.

The following is the degree form of Szemerédi’s famous Regularity Lemma. [14].

Lemma 1

(Regularity Lemma (Degree Form)-[1, 4]) For every $\epsilon > 0$, there is an $M = M(\epsilon )$ such that if G is any graph and $d\in (0,1)$ is any real number, then there is a partition of V(G) into $r+1$ clusters $V_{0},V_{1},\dots ,V_{r}$, and there is a subgraph $G^\prime \subseteq G$ with the following properties:

• (1) $r\le M$,

• (2) $|V_{0}|\le \epsilon |G|$,

• (3) $|V_{1}| = \dots = |V_{r}|=L \le \epsilon |G|$,

• (4) $\deg _{G^\prime }(v)>\deg _{G}(v)-(d+\epsilon )|G|$ for all $v\in V(G)$,

• (5) $e(G^\prime [V_i]) = 0$ for all $i \ge 1$,

• (6) for all $1\le i < j\le r$ the pair $(V_{i},V_{j})$ is $\epsilon$-regular in $G'$ and has density either 0 or greater than $d$.

Given a graph G and appropriate choices of $\epsilon$ and $d$, let $G^\prime$ be a spanning subgraph of G obtained from Lemma 1. The reduced graph $R = R(G,\epsilon ,d)$ of G contains a vertex $v_{i}$ for each cluster $V_{i}$ in $G^\prime {\setminus } V_0$ and has an edge between $v_{i}$ and $v_{j}$ if and only if $d(V_i,V_j) > d$. Hence, $V(R) = \{v_i \;|\; 1 \le i \le r\}$ and $E(R) = \{v_iv_j\;|\;1 \le i,j \le r, \; d(V_i,V_j) > d\}$. Note that $r= |R|$; the cluster $V_0$ does not correspond to a vertex in R.

We will also use the following one-sided version of regularity. Let $\epsilon , d> 0$. Given a graph G and two nonempty disjoint vertex sets $A, B \subset V$, we say that the pair (A, B) is $(\epsilon , d)$-super-regular if for every $X \subset A$ and $Y \subset B$ satisfying

$$\begin{aligned} |X|> \epsilon |A| ~ ~ ~ \text {and} ~ ~ ~ |Y| > \epsilon |B|, \end{aligned}$$

we have

$$\begin{aligned} e(X, Y) > d|X| |Y|, \end{aligned}$$

and furthermore $d_{B}(a) > d|B|$ for all $a \in A$ and $d_{A}(b) > d|A|$ for all $b \in B$.

As we will see, the condition of $(\epsilon ,d)$-super-regularity allows us to locate certain necessary short paths within a pair. Fortunately, we may create a super-regular pair from an $\epsilon$-regular pair by simply removing few vertices.

Fact 2

(Treglown [15], Lemma 1.8) Let (A, B) be an $\epsilon$-regular pair of density $d$. There exist subsets $A' \subseteq A$ and $B' \subseteq B$ with $|A'| \ge (1 - \epsilon )|A|$ and $|B'| \ge (1 - \epsilon )|B|$ such that $(A',B')$ is $(2\epsilon , d-3\epsilon )$-super-regular and $2\epsilon$-regular with density $d-3\epsilon$.

We have weakened the result in [15], which guaranteed $\frac{\epsilon }{1-\epsilon }$-regularity with density $d-3\epsilon$; for our purposes, having $2\epsilon$-regularity suffices. The proof of Fact 2 requires Fact 1, which guarantees that $(A',B')$ is $2\epsilon$-regular. From Fact 2, we can iteratively locate smaller and smaller $(\epsilon ',d')$-super-regular pairs within a large $(\epsilon ,d)$-super-regular pair.

Fact 3

Let (A, B) be an $(2\epsilon , d-3\epsilon )$-super-regular and $2\epsilon$-regular pair with density $d-3\epsilon$. For $\alpha > \frac{1}{2}$, there exist $A' \subseteq A$ and $B'\subseteq B$ with $|A'| \ge \alpha |A|$ and $|B'| \ge \alpha |B|$ such that $(A',B')$ is $(4\epsilon ,d-7\epsilon )$-super-regular.

Proof

Apply Facts 1 and 2 . $\square$

Note that Fact 3 is similar to Fact 1, but with super-regular pairs instead of regular pairs. The difference is that not every pair subset of (A, B) is super-regular; however, a super-regular pair does exist at every size. In Sect. 3, we repeatedly use Fact 3 immediately after creating our desired paths to ensure that the remaining vertices in each super-regular pair can still form a smaller, slightly less dense super-regular pair.

We now state the famous Blow-Up Lemma [8], which allows us to find any small subgraph of bounded degree within a super-regular pair. The last paragraph of Lemma 2, which implies Corollaries 3 and 4 , is from [7].

Lemma 2

(Blow-Up Lemma-Komlós et al. [7, 8]) Given a graph R of order r and positive parameters $d, \Delta ,$ there exists a positive $\epsilon = \epsilon (d, \Delta , r)$ such that the following holds. Let $\{n_{1},n_{2},\dots , n_{r}\}$ be an arbitrary set of positive integers and replace the set of vertices $\{v_{1},v_{2},\dots ,v_{r}\}$ of R with pairwise disjoint sets $V_{1}, V_{2}, \dots , V_{r - 1}$ and $V_{r}$ of sizes $n_{1},n_{2}, \dots , n_{r - 1}$ and $n_{r}$ respectively (blowing up). We construct two graphs on the same vertex-set $V = \cup V_{i}$. The first graph $\mathbf{R}$ is obtained by replacing each edge ${v_i,v_j}$ of R with the complete bipartite graph between the corresponding vertex-sets $V_i$ and $V_j$. A sparser graph G is constructed by replacing each edge ${v_i,v_j}$ arbitrarily with an $(\epsilon , d)$-super-regular pair between $V_i$ and $V_j$. If a graph H with $\Delta (H) \le \Delta$ is embeddable into $\mathbf{R}$ then it is also embeddable into G.

Furthermore, we can strengthen the assertion as follows. Suppose, for an $(\epsilon ,d)$-super-regular pair $(V_1,V_2)$ in G that a set $\{v_1,v_2\}\subseteq V(H)$ is given. Then we can find a copy of H in $G[V_1,V_2]$ with $v_1\in V_1$ and $v_2\in V_2$.

The last part of Lemma 2 leads to the following corollaries, which allow us to create both hamiltonian and short paths within super-regular pairs between specified vertices.

Corollary 3

For $0 < \epsilon \le d$, given an $(\epsilon , d)$-super-regular pair (A, B) with $|A| = |B|$ and a pair of vertices $a \in A$ and $b \in B$, there exists a hamiltonian a, b-path in (A, B).

We refer the reader to [7] (p. 140) for the proof, although we implement a nearly identical argument for the proof of Corollary 4.

Corollary 4

For $0 < \epsilon \le d$, given an $(\epsilon , d)$-super-regular pair (A, B) and a pair of vertices $a \in A$ and $b \in B$, there exists an a, b-path of length 3 in (A, B).

Proof

Let $A'\subseteq A$ and $B'\subseteq B$ be the neighborhoods of b and a, respectively. We have $|A' {\setminus } \{a\}| > \frac{d|A|}{2}$ and $|B' {\setminus } \{b\}| > \frac{d|B|}{2}$. Observe also, that the pair $(A{\setminus } a, B{\setminus } b)$ is $\left( 2\epsilon ,\frac{d}{2}\right)$-super-regular and hence contains an edge $a'b'$. The path $a-a'-b'-b$ is an a, b-path of length 3 in (A, B). $\square$

The following theorem gives us a lower bound on $\sigma _2(R)$ based on $\sigma _2(G)$.

Theorem 5

(Kühn et al. [10]) Given a constant c, if $\sigma _{2}(G) \ge cn$, then $\sigma _{2}(R) \ge (c - 2d- 4\epsilon )|R|$.

We also use the following theorem of Ore, letting n be the order of G.

Theorem 6

(Ore [13]) If G is 2-connected, then G contains a cycle of length at least $\min \{\sigma _{2}(G),n\}$.

Lastly, we use the following result of Williamson. Recall that a graph is called panconnected if, between every pair of vertices, there is a path of every possible length from 2 up to $n - 1$.

Theorem 7

(Williamson [16]) Let G be a graph of order n. If $\delta (G) \ge \frac{n + 2}{2}$, then G is panconnected.

3 Proof Outline

Given an integer $k \ge 3$, we choose constants $\epsilon$ and $d$ as follows:

$$\begin{aligned} 0 < \epsilon \ll d\ll \frac{1}{k^{2}}, \end{aligned}$$

where $a \ll b$ is used to indicate that a is chosen to be sufficiently small relative to b. Let $n = n(k) = n(k,\epsilon ,\delta )$ be sufficiently large to apply Lemma 1 with constants $\epsilon$ and $d$ to get large clusters and let R be the corresponding reduced graph. Note that, when applying Lemma 1, there are at least $\frac{1-\epsilon }{\epsilon }$ clusters so $|R| = r \ge \frac{1-\epsilon }{\epsilon }$. We then consider the desired path orders $n_{1}, n_{2}, \dots , n_{k}$ summing to n. As we will see from the proof of Theorem 2, obtaining paths with the correct number of vertices is always achievable once we make n sufficiently large to apply Lemma 1.

We use a sequence of lemmas to eliminate extremal cases of the proof. Without loss of generality, assume $n_{1} \le \dots \le n_{k}$. For Lemmas 3–5, assume the following: Given a positive integer k, let $\epsilon = \epsilon (k), d= d(\epsilon ) > 0$, and let G be a graph of order $n \ge n(k,\epsilon ,d)$ with $\sigma _2(G) \ge n+k-1$.

Our first lemma establishes the case when $\delta (G)$ is small.

Lemma 3

If $\delta (G) \le \frac{n_k}{8}$, then Conjecture 1 holds.

Lemma 3 is proven in Sect. 5. By Lemma 3, we may assume $\delta (G) \ge \frac{n_{k}}{8} \ge \frac{n}{8k}$. Our next lemma establishes the case when $\kappa (R) \le 1$.

Lemma 4

If $\kappa (R) \le 1$, then Conjecture 1 holds.

Lemma 4 is proven in Sect. 6. Our final lemma establishes the case where G contains a large independent set.

Lemma 5

Let $\lambda = \lambda (\epsilon ,d) < 4d+3\epsilon$. If $\alpha (G) \ge \left( \frac{1}{2} - \lambda \right) n$, then Conjecture 1 holds.

Lemma 5 is proven in Sect. 7.

With every lemma in place, use Ore’s Theorem (Theorem 6) to construct a long cycle in the reduced graph of G. Alternating edges of this cycle are then made into super-regular pairs of G. This structure is then used to construct the desired paths. The complete proof of our main result, assuming the above lemmas, is presented in the following section.

4 Proof of Theorem 2

By Lemma 3, we may assume $\delta (G) > \frac{n_{k}}{8}$. By Lemma 4, we may assume the reduced graph R is 2-connected. By Theorem 5 applied on G with $c = 1$, we know $\sigma _{2}(R) \ge (1 - 2d- 4\epsilon )r$. Thus, we may apply Theorem 6 to R (without the vertex corresponding to $V_{0}$) to obtain a cycle $C$ of length at least $(1 - 2d- 4\epsilon )r$ in R. Define a garbage set D to include all “misbehaving” vertices in G. Initially, let D include $V_{0}$ and those clusters not used in $C$. Currently, we have $|D| \le (2d+4\epsilon )n + |V_0| \le (2d+5\epsilon )n$.

Color the edges of $C$ red and blue such that no two red edges are adjacent and at most one consecutive pair of edges is blue (if |C| is odd). Apply Fact 2 on the pairs of clusters in G corresponding to the red edges of R to obtain $(2\epsilon ,d-3\epsilon )$-super-regular pairs where the two sets of each super-regular pair have the same order. (By Fact 1, each cluster pair is also $2\epsilon$-regular with density $d-\epsilon$.) All vertices discarded in this process are included in the garbage set D; define the clusters $C_{i}$ to be what remains of each cluster. Note that discarding these excess vertices from all $C_i$ results in at most $\epsilon n$ additional vertices included in the garbage set. Hence, we currently have $|D| \le (2d+6\epsilon )n$.

If C is odd, then consider the vertex in C with two blue edges, let $C_{0}$ be the corresponding cluster in G, and let $C_{0}^{+}$ and $C_{0}^{-}$ be the neighboring clusters in G. Recall that k is the number of paths we are trying to construct. Since the pairs $(C_{0}^{-}, C_{0})$ and $(C_{0}, C_{0}^{+})$ are both $2\epsilon$-regular and each cluster has order at most $\epsilon n$, there exists a set $T_0\subseteq C_{0}$ of k vertices with a matching to each of $C_{0}^{-}$ and $C_{0}^{+}$. In particular, one easy justification of this fact is to apply Fact 2 on each pair and use the resulting minimum degree conditions to produce the desired matchings. We use these matchings as transportation paths between $C_0^+$ and $C_0^-$ and move all of $C_{0} {\setminus } T_{0}$ to the garbage set D, which now has order at most $(2d+7\epsilon )n$.

Let $G_{C}$ denote the subgraph of G induced on the set of vertices remaining in clusters associated with $C$ that have not been moved to the garbage set. A path is said to balance a super-regular pair in $G_{C}$ if it uses an equal number of vertices from each set in the pair. A path that balances all its visited super-regular pairs is a balancing path. Note that the removal of each balancing path in $G_{C}$ preserves the fact that clusters in each super-regular pair have the same order and, by Fact 1, changes a pair from being $\epsilon$-regular with density $d$ (and hence containing a $(2\epsilon ,d-3\epsilon )$-super-regular pair) to being $2\epsilon$-regular with density $d-\epsilon$ (and hence containing a $(4\epsilon ,d-4\epsilon )$-super-regular pair). (Note that we may use Fact 1 because our balancing paths will always have length less than $2\epsilon |A|$.

For each chosen vertex $x_{i}$, if $x_{i} \notin V(G_{C})$, then use Menger’s Theorem [12] to construct a shortest path $P_i$ from $x_i$ to some vertex $x_{i}'$ in $G_{C}{\setminus } T_{0}$. In fact, since $\delta (G) \ge \frac{n_{k}}{8} \gg |D|$, these paths are all single edges. Using an edge of a super-regular pair first, construct a balancing path from $x_{i}'$ through every cluster of $G_{C}$. Otherwise, if $x_i\in V(G_{C})$, then simply construct a balancing path $P_i$ starting at $x_i$. Regardless of whether $x_i\notin V(G_{C})$ or $x_i\in V(G_{C})$, since each red cluster pair is $(2\epsilon ,d-3\epsilon )$-super-regular and each blue cluster pair has positive density, using Corollary 4, this balancing path can be constructed to use at most 2 vertices from each cluster. If this construction would yield a path that is longer than $n_{i}$, then simply terminate the path construction once the path length reaches $n_i$. (If such a termination would unbalance a cluster pair, then simply remove a vertex from the larger cluster to D. This adds at most k vertices to |D| and only negligibly affects regularity of any kind between the now-balanced clusters.) A path with $x_i$ as an endpoint (and hence, every balancing path $P_i$) is an $x_i$-path.

First suppose the $x_i$-path $P_i$ currently has order between $n_{i} - 17$ and $n_i$. In this case, we add at most 17 vertices using a super-regular pair (and Corollary 4) to finish creating $P_i$. If a coupled pair of clusters in $G_{C}$ is left unbalanced by this process, then we simply remove a vertex from the larger cluster to D. Note that repeating this for each short path adds at most $k - 1$ vertices to D and does not affect regularity of any kind between cluster pairs.

Let (A, B) be a super-regular pair of clusters in $G_{C}$. Note that this requires that A and B correspond to consecutive vertices on the cycle $C$. A balancing path starting in A and ending in B that contains a vertex $v \in D$ is called v-absorbing. If v is clear from context or is unspecified, then we may refer to a v-absorbing path as simply an absorbing path.

We now construct disjoint v-absorbing paths for the vertices $v \in D$. By doing so, we will include every vertex of D in some short path while still preserving the equality Disjoint absorbing paths are constructed iteratively, one for each vertex of D, in an arbitrary order. Suppose some number of such absorbing paths has been created. If we have created a disjoint v-absorbing path for each vertex $v \in D$ within the restrictions of the claim, the proof is complete so suppose we have constructed at most $|D| - 1$ absorbing paths. Vertices that have already been used on paths and clusters that have lost at least $\frac{(2d+ 7\epsilon )n}{81k dr}$ vertices are removed from consideration in the following iterations.

Claim 1

Given any vertex $v \in D$, avoiding any selected set of at most $1296 k dr$ clusters in $G_{C}$ and any set of at most $\frac{(2d+ 7\epsilon )n}{81k dr}$ vertices in each of the other (non-avoided) clusters of $G_{C}$, there exists a v-absorbing path of order at most 17. Otherwise the desired path partition already exists.

Proof

Recall that $d\ll 1$, and so $1296k d\ll 1$. Let $L'$ be the order of the smallest cluster in $C$. Recall that L is the order of each non-garbage cluster of G from Lemma 1 so $L \ge \frac{(1 - \epsilon ) n}{r}$. Recalling that we removed as many as $\epsilon L$ vertices from each cluster in C to ensure all pairs were $(2\epsilon , d-3\epsilon )$-super-regular, we have $L' \ge \frac{(1 - \epsilon )^{2} n}{r} - 2k \ge \frac{(1 - 2\epsilon ) n}{r} - 2k$ to avoid the vertices used in the $x_i$-paths.

Fact 4

If we have created at most $|D| - 1$ absorbing paths, then at most $1296 k dr$ clusters would have order at most $L' - \frac{(2d+ 7\epsilon )n}{81k dr}$.

Proof

Each absorbing path constructed in this claim has order at most 16 (other than the vertex v), so we lose at most 16 vertices from $G_{C}$ for each vertex of D. Since $|D| \le (2d + 7\epsilon )n$, the result follows. $\square$

Note that the remaining clusters would have remaining order at least

$$\begin{aligned} L' - \frac{16(2d+ 7\epsilon )n}{1296k dr} = L' - \frac{(2d+ 7\epsilon )n}{81 k dr} \ge L'\left( 1 - \frac{1}{9k} \right) \end{aligned}$$

since $d\gg \epsilon$.

Let $v \in D$ such that there is no absorbing path for v of order at most 17. Since $d(v) \ge \frac{n_{k}}{8} \ge \frac{n}{8k}$, v must have at least $\frac{n}{8kr} \ge \frac{L'}{9k} + 2$ edges to at least $\frac{r}{8k} \gg 1296k dr$ clusters. Let A and B be two clusters in $G_{C}$ which are not already ignored and in which v has at least two edges to vertices that are not already in an $x_i$-path or an absorbing path.

For convenience, we call two clusters X and Y a couple or spouses (in relation to each other) if X and Y are consecutive on $C$ and the pair (X, Y) is a super-regular pair. The following facts are easily proven using the structure we have provided and the lemmas proven before.

Fact 5

A and B are not a couple.

Otherwise, letting $a \in A$ and $b \in B$ be available neighbors of v, the path avb is a v-absorbing path.

Let $A'$ and $B'$ denote the spouses of A and B, respectively, and let $a',b'\in R$ correspond to $A'$ and $B'$, respectively. Similarly for another couple (P, Q) of clusters, let p and q be the corresponding vertices of R. Define the following sets of clusters:

• $X_A:=\{$spouses P, Q such that $pa'$ and $qa'$ are edges in $R\}$,

• $X_B:=\{$spouses P, Q such that $pb'$ and $qb'$ are edges in $R\}$, and

• $X_{AB}:=\{$spouses P, Q such that one of p or q has an edge to either $a'$ and $b'$ in $R\}$. In particular, let $X_{AB}'$ denote the clusters (either P or Q) in $X_{AB}$ that are not the neighbors of $A'$ and $B'$.

Since we are considering two neighbors of v in A (and two neighbors of v in B), say $v_{1}$ and $v_{2}$, if $X_{A}$ (or similarly $X_{B}$) contains even a single couple (P, Q), then since $(A,A')$, $(A',P)$, and (P, Q) are all super-regular of positive density, we know there has to be a path $v_1-v-v_2-A'-P-Q-A'$ (using distinct vertices in $A'$, of course). Thus, we may actually assume $X_{A} = X_{B} = \emptyset$.

Our next fact follows from the fact that $\sigma _{2}(R) \ge (1 - 2d- 4\epsilon )|R|$.

Fact 6

There are at most $(2d- 4\epsilon )|R|$ clusters in C which are not in $X_{AB}$.

If there is an edge xy between two (not already used in an absorbing or otherwise constructed path) vertices in clusters in $X_{AB}'$, then there is a v-absorbing path of the form $v_{1}-v-v_{2} - A' - (X_{AB} {\setminus } X_{AB}') - x-y - (X_{AB} {\setminus } X_{AB}') - A'$. Thus, the graph induced on the vertices in clusters in $X_{AB}'$ contains no edges. Considering Fact 6 and that $|D| \le 2d+7\epsilon$, by Lemma 5, we have the desired set of paths. This completes the proof of Claim 1. $\square$

By Claim 1, since $|D| \le (2d+ 7\epsilon )n$, we can construct disjoint v-absorbing paths for each vertex $v \in D$, and with a minimal effect on regularity of any kind between clusters in $G_C$ by Facts 1 and 2 . Let $P^{v}$ be an absorbing path for v with ends of $P^{v}$ in clusters $C_{j}$ and $C_{j + 1}$. Suppose uw is an edge of an $x_i$-path $P_{i}$ that passes from $C_{j}$ to $C_{j + 1}$. Then Corollary 4, we can replace the edge uw with the path $P^{v}$ with the addition of at most 2 extra vertices at either end. Note that absorbing a vertex $v \in D$ into a path $P_{i}$ using the absorbing path will always change the parity of the length of $P_{i}$.

For each path $P_{i}$ that is not already completed and such that $n_i-|P_i|$ is odd, absorb a single vertex from D into $P_{i}$. This will cause $n_i-|P_i|$ to be even.

Recall the assumption (without loss of generality) that $n_1 \le \dots \le n_k$. All remaining vertices of D can be absorbed into $P_{k}$. This makes $|P_{k}|$ larger, but since $|D| \le (2d+ 7\epsilon )n$ and each absorbing path $P^{v}$ for $v \in D$ has order at most 17 with at most two extra at either end, we get $|P_{k}| \le 2|C| + 17(2d+ 7\epsilon )n \ll \frac{n}{k} \le n_{k}$. (Recall that each path $P_i$ winds around C at most twice, which requires the “2|C|” part of the bound.) Note that $|C| \le |R|$, and so |C| is not a fraction of n.

At this point, let us recall the paths we have created. For each i, we have an $x_i$-path $P_i$ that winds around $C$ once (and hence contains at most 2 vertices in every cycle cluster). Additionally, the $x_k$-path $P_k$ contains all non-$x_i$ vertices in D (except for the few absorbing paths that are a part of an $x_i$-path $P_i$ to ensure that $n_i - |P_i|$ is even for all i) but still has order significantly less than the desired $n_k$. We will repeatedly use Facts 1 and 2 to finish each $x_i$-path $P_i$.

$(*)$ Consider an unfinished $x_i$-path $P_i$ with lowest index i and two of its vertices $c_j$ and $c_{j+1}$ in $C_j\cap P_i$ and $C_{j+1}\cap P_i$, respectively, where $(C_j,C_{j+1})$ is a couple in $G_{C}$. We consider three cases, depending on the number of vertices we need to include to $P_i$ so that $|P_i| = n_i$. Remember that $|C_j| = |C_{j+1}|$ for all couples $(C_j,C_{j+1})$, as we have only excluded vertices in v-absorbing paths, which are balancing paths.

Case 1

$n_i - |P_i| \ge |C_j| + |C_{j+1}|$

By Corollary 3, there exists a $c_j,c_{j+1}$-path Q in $(C_j,C_{j+1})$ that contains all remaining vertices in $(C_j,C_{j+1})$. Within $P_i$, replace the edge $c_jc_{j+1}$ with Q. Every vertex in $C_j$ and $C_{j+1}$ is now a part of $P_i$. Now consider another super-regular cluster $(C_p,C_{p+1})$ and return to ($*$) with the pair $(C_p,C_{p+1})$ in place of $(C_j,C_{j+1})$ (but $P_i$ remaining the same).

Case 2

$\frac{1}{2}(|C_j| + |C_{j+1}|)< n_i - |P_i| < |C_j| + |C_{j+1}|$

By Fact 3, there exists a $(4\epsilon , d- 7\epsilon )$-super-regular pair $(A_j,A_{j+1})\subset (C_j,C_{j+1})$ of order $\frac{1}{2}(n_i - |P_i|)$ containing $c_j$ and $c_{j+1}$. Hence, by Corollary 3, there exists a $c_j,c_{j+1}$-path Q in $(C_j,C_{j+1})$ that contains all but at most $\frac{1}{2}(|C_j| + |C_{j+1}|)$ vertices in $(C_j,C_{j+1})$. Within $P_i$, replace the edge $c_jc_{j+1}$ with Q. Similar to the proof of Fact 3 by replacing $\alpha > \frac{1}{2}$ with $\alpha > c$ for some constant $c \gg d$, we can conclude that $(C_j{\setminus } A_j,C_{j+1}{\setminus } A_{j+1})$ is also $(c_{1}\epsilon , d- c_{2}\epsilon )$-super-regular for small constants $c_{1}$ and $c_{2}$. Note that since we repeat this process at most k times, the density will remain bounded away from 0, so we can always find $c > 0$ such that $\alpha > c$, even at the last iteration. Hence, replace $(C_j,C_{j+1})$ with $(C_j{\setminus } A_j,C_{j+1}{\setminus } A_{j+1})$ for future cases.

Consider a different pair $(C_p,C_{p+1})$, and proceed to Case 3 to finish completing path $P_i$.

Case 3

$n_i - |P_i| \le \frac{1}{2}(|C_j| + |C_{j+1}|)$

By Fact 3, there exists a $(4\epsilon , d- 7\epsilon )$-super-regular pair $(A_j,A_{j+1})\subset (C_j,C_{j+1})$ of order $n_i - |P_i|$ containing $c_j$ and $c_{j+1}$. Hence, by Corollary 3, there exists a $c_j,c_{j+1}$-path Q in $(C_j,C_{j+1})$ that contains all remaining vertices in $(C_j,C_{j+1})$. Within $P_i$, replace the edge $c_jc_{j+1}$ with Q. By the same argument as in the previous case, we get that $(C_j{\setminus } A_j,C_{j+1}{\setminus } A_{j+1})$ is also $(c_{1}\epsilon , d- c_{2}\epsilon )$-super-regular for small constants $c_{1}$ and $c_{2}$. Hence, replace $(C_j,C_{j+1})$ with $(C_j{\setminus } A_j,C_{j+1}{\setminus } A_{j+1})$ for future cases.

Once $P_i$ is completed, return to $(*)$ and repeat until $|P_i| = n_i$ for all i. We are able to continually repeat Cases 1–3 because Facts 1 and 2 consistently guarantee the existence of super-regular pairs outside of the ad-hoc path Q. Additionally, until we reach $P_k$, there are always approximately $\frac{|R|}{k}$ unused cluster pairs $(C_j,C_{j+1})$ because $n_k \ge \frac{1}{k}$. As a result, completing $P_k$ will only involve Case 1. $\square$

5 Proof of Lemma 3

Recall that Lemma 3 claims Conjecture 1 holds when $\delta (G) \le \frac{n_{k}}{8}$.

Proof

Let $a \in V(G)$ with $|N(a)|=\delta (G) \le \frac{n_{k}}{8}$, and partition V(G) as follows:

$$\begin{aligned} B= & {} G {\setminus } (\{a\} \cup N(a)),\\ A= & {} \left\{ v \in \{a\} \cup N(a): |N(v) \cap V(B)| < \frac{1}{8}(n+k-\delta (G)-1) \right\} ,\\ C= & {} \left\{ v \in \{a\} \cup N(a): |N(v) \cap V(B)| \ge \frac{1}{8}(n+k-\delta (G)-1) \right\} . \end{aligned}$$

Note that, since $\sigma _2(G) \ge n+k-1$, the set A induces a complete graph. Furthermore, the set B has order $n-1-\delta (G)$ and A is nonempty since $a \in A$. Since $\sigma _{2}(G) \ge n + k - 1$ and a has no edges to B, each vertex in B has degree at least $n + k - 1 - \delta (G)$ which means $\delta (G[B]) \ge n + k - 1 - 2\delta (G)$. Note that G is also $(k + 1)$-connected. First, a claim about subsets of B.

Claim 2

Every subset of B of order at least $\frac{3n_{k}}{8}$ is panconnected.

Proof

With $|B| = n - \delta (G) - 1$ and $\delta (G[B]) \ge n + k - 1 - 2\delta (G)$, we see that $\delta (G[B]) \ge |B| - \delta (G) \ge |B| - \frac{n_{k}}{8}$. Therefore, for any subset $B' \subseteq B$ with $|B'| \ge \frac{3n_{k}}{8}$, we have $\delta (G[B']) \ge |B'| - \frac{n_{k}}{8} > \frac{|B'| + 2}{2}$. By Theorem 7, we see that $B'$ is panconnected. $\square$

Consider k selected vertices $X = \{x_1, \dots , x_k\} \subseteq V(G)$. Let $X_{A}$ denote the (possibly empty) set $X \cap A$ and let $X_{A}'$ denote $X_{A} \cup v$ where $v \in A {\setminus } X_{A}$ if such a vertex v exists. If no such vertex v exists, then let $X_{A}' = X_{A}$. The vertices of $X_{A}'$ will serve as start vertices for paths that will be used to cover all of A. By Menger’s Theorem and since $\kappa (G) \ge k + 1$, there exists a set of disjoint paths ${\mathscr {P}}_{A}$ starting at the vertices of $X_{A}'$ and ending in B and avoiding all other vertices of X. Choose ${\mathscr {P}}_A$ so that each path is as short as possible, contains only one vertex in B and, by construction, has order at most 3. If any of the paths in ${\mathscr {P}}_{A}$ begins at a selected vertex $x_{i}$ and has order at least $n_{i}$, we call this desired path completed and remove the first $n_{i}$ vertices of the path from the graph and continue the construction process. If $A {\setminus } V({\mathscr {P}}_{A}) \ne \emptyset$, let $P_{v}$ be a path using all remaining vertices and ending at v. This path $P_{v}$ together with the path of ${\mathscr {P}}_{A}$ corresponding to v provides a single path that cleans up the remaining vertices of A and ends in B. The ending vertices of these paths, the vertices of B, will serve as proxy vertices for the start vertices (v or $x_{i} \in X \cap A$). Thus far, we have constructed paths that cover all of A, start at vertices of $X \cap A$ (when such vertices exist) and end in B, along with possibly one path starting at v.

As vertices of B are selected and used on various paths, we continuously call the set of vertices in B that have not already been prescribed or otherwise mentioned the remaining vertices in B. For example, so far $B {\setminus } (X \cup V({\mathscr {P}}_{A}))$ is the set of remaining vertices of B. Our goal is to maintain at least $\frac{3n_{k}}{8}+1$ remaining vertices to be able to apply Claim 2 as needed within these remaining vertices.

Since $|C| \le \delta (G) \le \frac{n_{k}}{8}$ and $d_{B}(u) \ge \frac{1}{8} (n + k - \delta (G) - 1)$ for all $u \in C$, there exists a set of two distinct neighbors in $B {\setminus } (X \cup V({\mathscr {P}}_{A}))$ for each vertex in C. For each vertex $x_{i} \in X \cap C$, select one such vertex to serve as a proxy for $x_{i}$ and leave the other aforementioned neighbor in the remaining vertices of B. By Claim 2, there exists a path through the remaining vertices of B with at most one intermediate vertex from one neighbor of a vertex of C to a neighbor of another vertex of C. Since $|C| \le \frac{n_{k}}{8}$, such paths can be built and strung together into a single path $P_{C}$ starting and ending in B, containing all vertices of $C {\setminus } X$ with $|P_{C}| < 4 |C| \le \frac{n_{k}}{2}$.

We may now construct what is left of the desired paths within B. The paths $P_{1}, P_{2}, \dots , P_{k - 1}$ can be constructed in any order starting at corresponding proxy vertices and ending at arbitrary remaining vertices of B using Claim 2 in the remaining vertices of B. Finally, there are at least

$$\begin{aligned}&|B| - \left| B \cap \left( \cup _{i = 1}^{k - 1} V(P_{i})\right) \right| - |B \cap V({\mathscr {P}}_{A})| - |B \cap V(P_{C})|\\&\ge (n - 1 - \delta (G)) - (n- 1 -\delta (G) - n_k) - (k + 1) - (3|C|)\\&> \frac{3n_{k}}{8} + 1 \end{aligned}$$

remaining vertices in B. With these and Claim 2, we construct a path with at most one internal vertex from an end of $P_{C}$ to the proxy of v (if such a vertex exists) and a path containing all remaining vertices of B from $x_{k}$ (or its proxy) to the other end of $P_{C}$. This completes the construction of the desired paths and thereby completes the proof of Lemma 3. $\square$

6 Proof of Lemma 4

Assume $\sigma _{2}(G) \ge n + k - 1$. We begin with a result ensuring that low connectivity in the reduced graph R results in at most two components after the removal of a minimum cut set.

Lemma 6

Let $\epsilon ,d > 0$ be small real numbers and k be a positive integer. If G is a graph with $\sigma _2(G) \ge n+k-1$ and reduced graph $R=R(G,\epsilon ,d)$ with connectivity at most 1, then R consists of only two components after the removal of a minimum cut set.

Proof

Applying Lemma 1 to G, let $G''=G'[V(G){\setminus } V_0]$. Since $d_{G''}(v) > d_G(v) - (d+2\epsilon )n$ for all $V(G'')$, it immediately follows from Theorem 5 that $\sigma _2(R) > (1 - 2(d+2\epsilon ))|R|$. Let D be a minimum cutset of R (if one exists) so $|D| \in \{0, 1\}$. Suppose $R{\setminus } D$ contains at least three components, three of which being A, B, and C. Let $a\in A$, $b\in B$ and $c\in C$. Then $d(a)+d(b) > (1-2(d+2\epsilon ))|R|$, which implies $|A|+|B| > (1-2(\delta +2\epsilon ))|R| - 2|D|$. Similarly, the same is true for $|B|+|C|$ and $|A|+|C|$. Finally $2(|R {\setminus } D|) \ge 2(|A|+|B|+|C|) > 3(1-2(d+2\epsilon ))|R| - 6|D|$, or $|D| > \frac{1}{4}(1-2(d+2\epsilon ))|R|$, a contradiction. $\square$

Remark 1

Given small real numbers $\epsilon , d > 0$ and a positive integer k, let G be a graph of order $n = \sum _{i=1}^k n_i \ge n(\epsilon ,d,k)$ with $\sigma _2(G) \ge n+k-1$ and $\delta (G) \ge \frac{n_k}{8}$. Let $G'$ be the subgraph of G from Lemma 1 and let $E'$ be the set of edges that were removed from G to obtain $G'$. We replace the smallest set of edges M possible (from $E'$ back into $G'$) to recover the condition that $\kappa (G') \ge k + 1$. Note that such a set of edges M is indeed a matching since otherwise, given $\delta (G') \ge \frac{n_k}{8}-(d+\epsilon )n$, we could contradict the minimality of either M or C. Since the reduced graph R of $G'$ is assumed to have connectivity at most one, let $D\subset V(G')$ be the cluster corresponding to a cut vertex of R. (If R contains no cut vertices, then $D=\emptyset$.) Let $V_0$ be the garbage cluster of $G'$ resulting from Lemma 1, and let C be a minimum cutset of $G'$. By Lemma 1, each vertex of R corresponds to a cluster in $G'$ of order $L \le \epsilon n$. Since there is a cutset containing $D\cup V_0 \cup V(M)$, we have $k + 1 \le |C| \le |D| + |V_0| + 2 (k + 1) \le 3 \epsilon n$. By Lemma 6, we may define A and B to be the two components of $G'{\setminus } C$ and write $G'=A\cup C\cup B$. It immediately follows from $\sigma _2(G)\ge n+k-1$ that $\sigma _{2}(G') \ge n + k - 1 - 2(d + 3\epsilon ) n$ and

$$\begin{aligned} \begin{aligned} \delta \left( G'[A] \right)&> |A|-|C| - 2(d + 3\epsilon ) n \ge |A| - 3(d + 4\epsilon ) n, \\ \delta \left( G'[B] \right)&> |B|-|C| - 2(d + 3\epsilon ) n \ge |B| - 3(d + 4\epsilon ) n. \end{aligned} \end{aligned}$$

(1)

From the assumption that $\delta (G) \ge \frac{n_k}{8} \ge \frac{n}{8k}$ (Lemma 3), we know $|A|,|B| \ge \frac{n_k}{8} - |C| - 2(d + 3\epsilon ) n \ge \left( \frac{1}{8k}- (2d+9\epsilon ) \right) n > \frac{n}{8(k+1)}$.

While panconnected sets give paths of arbitrary length, only the endpoints are specified. Hence, to create disjoint paths of arbitrary length, we must create sets using vertices that are not part of an already existing desired path. Fortunately, even small subsets of A and B induce panconnected graphs.

Lemma 7

Let $\epsilon$, d, k, and $G'=A\cup C\cup B$ be defined as in Remark 1. Then the induced graph on any subgraph of A or B of order at least $4(d + 4\epsilon ) n$ is panconnected.

Proof

We see from (1) that $\delta (G'[A]) > |A| - 3(d + 4\epsilon ) n$. Then for all $U\subset A$ of order at least $4(d + 4\epsilon ) n$, we have

$$\begin{aligned} \begin{aligned} \delta (G'[U])&\ge |U|-3(d + 4\epsilon ) n+1 \\&\ge \frac{|U|+2}{2}. \end{aligned} \end{aligned}$$

By Theorem 7, the graph $G'[U]$ is panconnected. A symmetric argument shows that if $U\subset B$ has order at least $4(d+4\epsilon )n$, then $G'[U]$ is panconnected. $\square$

With this information, we prove the following lemma which completes the proof of Lemma 4.

Lemma 8

Given small real numbers $\epsilon , d > 0$ and a positive integer k, let G be a graph of order $n = \sum _{i=1}^k n_i \ge n(\epsilon ,d,k)$ with $\sigma _2(G) \ge n+k-1$ and $\delta (G) \ge \frac{n_k}{8}$. If $\kappa (R) \le 1$, then the conclusion of Theorem 2 holds.

Proof

Suppose $\kappa (R) \le 1$, and let $G'=A\cup C\cup B$ as in Remark 1. As noted before (1), we know $k + 1 \le |C| \le 3\epsilon n$. As noted after (1), we know $|A|,|B| > \frac{n}{8(k+1)}$. Since C is a minimum cut set, for each vertex $c\in C$, we may reserve two unique neighbors $a_c\in A$ and $b_c\in B$ that are not both in X. Call $A_C = \{a_c\in A \;|\; c\in C\}$ (symmetrically $B_C = \{b_c\in B \;|\; c\in C\}$) the set of proxy vertices in A (symmetrically B). Hence, we have $|A_C| = |B_C| = |C| =\kappa (G) \ge k+1 = |X| + 1$, which means that at least one vertex $c^*\in C$ has both $a_c^*$ and $b_c^*$ not in X. More specifically, the sets $A_C$ and $B_C$ can be created so that the number of triples $\{a_c,c,b_c\}$ not containing a vertex in X is

$$\begin{aligned} k+1 - |X\cap A_C| - |X\cap C| - |X\cap B_C| \ge 1. \end{aligned}$$

(2)

Recall from Sect. 4 that an x-path is a path containing a vertex x as an endpoint. Namely, each desired path $P_i$ in $G'$ is an $x_i$-path.

Set aside the set $T_A\subset A{\setminus } (X\cup A_C)$ of order $5(d+4\epsilon )n$; this set will serve as the potential transportation between $X\cap A$ and C. Set aside an analogous set $T_B\subset B{\setminus } (X\cup B_C)$. Begin with $i=1$, and repeat this process for the next-lowest value of i. Let ${\mathscr {P}}_i = \bigcup _{j=1}^{i-1} P_{j}$ be the collection of previous $x_j$-paths before $P_i$.

Without loss of generality, assume $x_k\in A\cup C$, and that if $x_k\in C$, then the proxy vertex in $A_C$ corresponding to $x_i$ is not in X. If $n_i \le |A{\setminus } (X\cup A_C\cup T_A\cup {\mathscr {P}}_i)| - 5(d+4\epsilon )n$, then use Lemma 7 to create the path $P_i$ entirely in $A{\setminus } (X\cup A_C\cup T_A\cup {\mathscr {P}}_i)$ with the possible exception of $x_i$ and its neighbor (if $x_i\in A_C$ or $x_i\in C$).

If $n_i > |A{\setminus } (X\cup A_C\cup T_A\cup {\mathscr {P}}_i)| - 5(d+4\epsilon )n$, then we must do several things at once. For each $x_j\in A{\setminus } A_C$, use Lemma 7 to create an $x_j$-path of length 4 through $T_A$ then $A_C$ then C then $B_C$. By (2), we can guarantee that each vertex $x_i$ corresponds to a triple $\{a_c,c,b_c\}$ with no vertices in X. For each $x_i\in A_C$, use Lemma 7 to create an $x_j$-path of length 2 through C then $B_C$. By the definition of $A_C$ and $B_C$, we know that the corresponding proxy vertex in $B_C$ cannot be in X. For all $x_j\in C$, create an $x_j$-path of length 1 through $B_C$ if $b_{x_j}\notin X$. If $b_{x_j}\in X$, then create the $x_j$-path through $A_C$ then $T_A$ then $A_C$ then C then $B_C$; since both $x_j, b_{x_j}\in X$, there is a corresponding triple $\{a_c,c,b_c\}$ with no vertices in X. Now that we have taken care of all vertices in $X\cap (A\cup C)$, create the path Q as follows. Use Lemma 7 repeatedly so that Q contains all remaining vertex triples $\{a_c,c,b_c\}$ having no vertices in X, all of $T_A$ and $T_B$, and any extra vertices in $A_C{\setminus } X$ and $B_C{\setminus } X$. In particular, the triple $\{a_c^*,c^*,b_c^*\}$ has no vertices in X and guarantees that Q passes through A, C, and B. Form Q as follows: Include all vertices $a_c$ with $c\in X$ (and hence, the same number of vertices in $T_A$). End this short path with a vertex $a_c\in A_C$ such that $\{a_c,c,b_c\}\cap X = \emptyset$. From $a_c$, include c and then $b_c$, and then use Lemma 7 to include a vertex from $T_B$ and another triple $\{b_c',c',a_c'\}$ not intersecting X. Continue weaving this path between A, C, and B until all triples not in X are included. Then repeatedly use Lemma 7 to include all vertices in $B_C{\setminus } X$ and $T_B$. Note that $|Q| < |T_A| + |T_B| + |A_C| + |B_C| + |C| \le 10(d+4\epsilon )n + 9\epsilon n \ll n/k \le n_1$. At this point, the only vertices in A not included in some $x_j$-path are vertices in $A{\setminus } (X\cup A_C\cup T_A\cup {\mathscr {P}}_i)$ and $B{\setminus } (X\cup B_C\cup T_B\cup {\mathscr {P}}_i)$. From here, complete $P_i$ by using Lemma 7 and all remaining paths $P_j$, adjoining Q to $P_k$. Note that we are able to repeatedly use Lemma 7 to create $P_i$ through $P_i$ since there are well over the required $4(d+4\epsilon )n$ vertices in $B{\setminus } (X\cup A_C\cup T_A\cup {\mathscr {P}}_2)$. $\square$

7 Proof of Lemma 5

Recall that Lemma 5 says for a positive integer k, small $\epsilon = \epsilon (k) > 0$ and $d= d(k) > 0$, and $\lambda = \lambda (\epsilon ,d) < 4d+3\epsilon$, a graph G of order $n \ge n(\lambda )$, if $\sigma _2(G) \ge n + k - 1$ and $\alpha (G) \ge \left( \frac{1}{2} - \lambda \right) n$, then G satisfies Conjecture 1.

Proof

Let A be a maximum independent set of G, and let $B = V(G) {\setminus } A$. By the assumption on $\sigma _2(G)$, we have $|B| \ge \frac{1}{2}(n + k - 1)$. This implies

$$\begin{aligned} \left( \frac{1}{2} - \lambda \right) n \le |A| \le \frac{1}{2}(n - k + 1) \end{aligned}$$

and

$$\begin{aligned} \frac{1}{2}(n + k - 1) \le |B| \le \left( \frac{1}{2} + \lambda \right) n. \end{aligned}$$

Claim 3

Let $B'$ be the set of vertices in B each with at least $\xi n$ neighbors in A. Then $|B'| \ge \left( \frac{1}{2}-\frac{\xi \lambda }{9k^9}\right) n$.

Proof

Each vertex in A (except possibly one) has at least $\frac{1}{2}(n+k-1)$ neighbors in B, which means there are at least $(|A|-1)\cdot \frac{1}{2}(n+k-1)$ edges between A and B. On the other hand, there are fewer than $|B'||A| + |B {\setminus } B'| \left( \frac{1}{2} - \frac{1}{16k} \right) n$ edges out of B. This gives

$$\begin{aligned} \frac{1}{2}(|A|-1)(n+k-1) \le |B'||A| + (|B|-|B'|)\xi n. \end{aligned}$$

Solving for $|B'|$, letting $|B| = n - |A|$, and substituting $|A| \ge (1/2 - \lambda )n$ in the denominator, we have

$$\begin{aligned} \begin{aligned} |B'|&\ge \frac{1/2(|A|-1)(n+k-1) - |B|\xi n}{|A|-\xi n} \\&\ge \left( \frac{1}{2}+\xi \right) n + \frac{\xi (\xi -1/2)n^2}{(1/2-\xi )n-(k-1)/2}\\&\ge \left( \frac{1}{2}-\frac{\xi \lambda }{9k^9}\right) n. \end{aligned} \end{aligned}$$

$\square$

By Claim 3, we have

$$\begin{aligned} |B{\setminus } B'|\le & {} \left( \frac{1}{2} + \lambda \right) n - \frac{1}{2}\left( 1 - \frac{\lambda }{9k^9}\right) n \\ ~= & {} \left( 1-\frac{1}{18k^9}\right) \lambda n \\ ~< & {} \lambda n. \end{aligned}$$

Let M be a maximum matching between $B{\setminus } B'$ and A and let D be the vertices of $B{\setminus } B'$ that are not covered by M. In particular, vertices in D must have at least $\left( \frac{1}{2} - 2\lambda \right)$ neighbors in B. Hence, we will frequently refer to $A\cup D$, as every vertex in this set has at least $\left( \frac{1}{2}-\frac{1}{16k}-\lambda \right) n$ neighbors in $B'$. Let $\tau$ be the number of edges in $B{\setminus } D$ that must be included in the paths $P_1$ through $P_k$—all other edges in these paths will be in $A\cup D$ and $B{\setminus } D$. Letting $o(S) = |\{x_i\in S \;|\; n_i is odd \}|$, we get

$$\begin{aligned} \begin{aligned} \tau&= |B {\setminus } D| - |A \cup D| + o(A \cup D) - o(B {\setminus } D) \\&= |B| - |A| - 2|D| + o(A \cup D) - o(B {\setminus } D). \end{aligned} \end{aligned}$$

(3)

By definition, there are no edges from D to $A {\setminus } V(M)$. Hence, if we pick two vertices u and v in $A {\setminus } V(M)$, then we get $d(u) + d(v) \le 2|B {\setminus } D|$, but since $\sigma _{2}(G) \ge n + k - 1$, this means

$$\begin{aligned} |B| - |A| -2|D| \ge k - 1. \end{aligned}$$

From (3), we get $\tau \ge -1$.

We first assume $\tau \ge 0$ and build the desired paths. We will address the case $\tau = -1$ in Claim 5 later.

Let $\xi = \frac{1}{2} - \frac{1}{16k}$; i.e., each vertex in $B'$ misses at most $\frac{1}{16k}n$ vertices in A. From the condition $\sigma _2(G)\ge n+k-1$, each vertex in $D'$ has at least $\left( \frac{1}{16k} -2\lambda \right) n$ neighbors in $B'$.

A bipartite graph $U\cup V$ is bipanconnected if for every pair of vertices $x,y\in U\cup V$, there exist (x, y)-paths of all possible lengths at least 2 of appropriate parity in $U\cup V$. That is, for every pair of vertices $x\in U$ and $y\in V$, there exist (x, y)-paths of every possible odd length except 1, and for every pair of vertices $x,y\in U$ (and V), there exist (x, y)-paths of every even length. Note that we must exclude the value 1 from our definition in order to allow graphs $U\cup V$ that are not complete bipartite. Also observe that the sets U and V need not be balanced, so the longest possible length may be only $2\min \{ |U|, |V| \}$. We state a helpful fact that is easily proven using standard extremal arguments.

Fact 7

(Coll et al. [3]) If $G[U \cup V]$ is a balanced bipartite graph of order 2m with $\delta (G[U \cup V]) \ge \frac{3m}{4}$, then $G[U \cup V]$ is bipanconnected.

Our next claim shows that any reasonably large subsets of $B'$ induce bipanconnected subgraphs when paired with any corresponding subset of A.

Claim 4

For all $m \ge \frac{n}{4k}$, if $U\subseteq A\cup D$ and $V\subseteq B'$ with $|U|, |V| \ge m$, then $U \cup V$ induces a bipanconnected subgraph of G.

Proof

For $m \ge \frac{n}{4k}$, let U and V be subsets of A and $B'$ respectively with $|U|, |V| \ge m$. Since each vertex in $A\cup D$ has at least $(1/2-\frac{1}{16k}-\lambda )n$ neighbors in B , each vertex in U has at least $|V| - 2\lambda n > \frac{3m}{4}$ neighbors in V. Each vertex in V has degree at least $|U| - \frac{1}{16k} n \ge \frac{3m}{4}$ into U. It follows from Fact 7 (simply removing vertices from the larger set if the sets are not balanced) that $G[U \cup V]$ is bipanconnected. $\square$

Each vertex of $D'$ is incident to at least $\left( \frac{1}{16k}-2\lambda \right) n$ neighbors in $B'$. For all vertices in $D'{\setminus } X$, set aside two unique neighbors within $E(B')$; set aside one unique neighbor for each $x_i\in D'$. If $\tau$ is larger than $|D'|$, then the condition $\sigma _2(G)\ge n+k-1$ applied to vertices in $B'$ provides at least $\tau - |D'|$ disjoint edges within E(B). Finally, applying Claim 4, we may construct each desired path $P_i$ starting at $x_i$, with the prescribed length. When necessary, include one of the $\tau$ edges in $B'\cup D'$ meant to correct potential parity issues between $n_i$ and $|B'\cup D'| - |A\cup D|$. We construct these paths in order from shortest to longest so that, when constructing the final path, there will certainly be enough vertices remaining to apply Claim 4. For all $x_i$ incident to an edge in the matching M, begin $P_i$ with the corresponding edge in M so as to use up the corresponding vertex in D (or A). For $P_k$, the last (i.e., longest) path, include all that remains of the matching M between $D'$ and A. This completes the proof in the case when $\tau \ge 0$. We now show that this assumption is justified.

Claim 5

We may assume $\tau \ge 0$.

Proof

Suppose $\tau = -1$, which means that $n_i$ is odd for all i and $X\subseteq B {\setminus } D'$. If the set $A \cup D$ must contains even a single edge, then we may use that edge to construct $P_1$ through $P_k$, with all other edges being between $(A\cup D)$ and $B'\cup D'$. So assume $A\cup D$ is independent, which by the choice of A with $|A| = \alpha (G)$ gives $D = \emptyset$. This gives us $|B| = |A| + k - 1$, which means $A \cup B$ induces a complete bipartite graph.

If k is even, then n is even (since $n = \sum n_{i}$), but $n = |A| + |B| = 2|A| + k - 1$, which is odd, a contradiction. If k is odd, then n is odd, but $n = 2|A| + k - 1$, which is even, again a contradiction. This completes the proof of Claim 5. $\square$

This also completes the proof of Lemma 5. $\square$