Bounds for Judicious Balanced Bipartitions of Graphs

Abstract

A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. Bollob$\acute{a}$s and Scott proved that every regular graph with m edges admits a balanced bipartition $V_{1}$, $V_{2}$ of V(G) such that $\max \{e(V_{1}), e(V_{2}) \}< \frac{m}{4}$. Only allowing $\varDelta (G)-\delta (G)$ =1 and 2, Yan and Xu, and Hu, He and Hao, respectively showed that a graph G with n vertices and m edges has a balanced bipartition $V_{1}$, $V_{2}$ of V(G) such that $\max \{e(V_{1}), e(V_{2}) \}\le \frac{m}{4}+O(n)$. In this paper, we give an upper bound for balanced bipartition of graphs G with $\varDelta (G)-\delta (G)=t-1$, $t\ge 2$ is an integer. Our result extends the conclusions above.

1 Introduction

Graphs considered in this paper are finite and simple. For general theoretic notations, we follow Bondy and Murty [4]. Throughout the paper, the letter G denotes a graph. For $u \in V(G)$, denote by $N_{G}(u)$ and $d_{G}(u)$ the set of neighbors of u and the degree of u in G, respectively. The maximum degree of G is denoted by $\varDelta (G)$ and minimum degree of G is denoted by $\delta (G)$ analogously. We use e(G) to denote the number of edges of G.

Let G be a graph and k a positive integer. A k-partition of G is a partition of V(G) into k pairwise disjoint nonempty sets. A 2-partition is usually referred to as a bipartition. Let $V_{1}, V_{2},\ldots ,V_{k}$ be a k-partition of G. For $1\le i \le k$, we use $e(V_{i})$ to denote the number of edges with both ends in $V_{i}$, and use $e(V_{i},V_{j})$ to denote the number of edges with one end in $V_{i}$ and the other in $V_{j}$. For $\{i_{1},i_{2},\ldots ,i_{h}\} \subseteq \{1,2,\ldots ,k\}$, let $e(V_{i_{1}},V_{i_{2}},\ldots ,V_{i_{h}})= \sum _{i\ne j\in \{i_{1},i_{2},\ldots ,i_{h}\}}e(V_{i},V_{j})$, and accordingly we call $e(V_{1},V_{2},\ldots ,V_{k})$ the size of the partition.

The maximum bipartite subgraph (MBS) problem is a classic problem in graph theory. Given a graph G, the goal of MSB is to ask for a bipartition $V_{1}, V_{2}$ of V(G) maximizing $e(V_{1}, V_{2})$. In theory, this problem equivalently finding the minimum of $e(V_{1})+e(V_{2})$ over all partitions $V(G)=V_{1} \cup V_{2}$. Judicious partition problem [2] asks for a bipartition of the vertex set of a graph into subsets such that several quantities are optimized simultaneously. The Bottleneck Bipartition problem [7] is such an example: Given a graph, find a partition $V_{1},V_{2}$ of V(G) that minimizes $\max \{e(V_{1}),e(V_{2})\}$. Porter [6] proved that for any graph G with m edges there is a bipartition $V_{1},V_{2}$ of V(G) such that max $\{e(V_{1},V_{2})\}\le \frac{m}{4}+O(\sqrt{m})$. Then, Xu and Yu [8] extended this result to k-partition.

Bollob$\acute{a}$s and Scott first studied Bottleneck problem with the additional requirement that the bipartition is balanced and posed the following conjecture.

Conjecture 1

[2] Let G be a graph with minimum degree at least 2. Then V(G) admits a balanced bipartition $V_{1},V_{2}$ such that $\max \{e(V_{1}),e(V_{2})\} \le e(G)/3$.

Xu and Yu [8] first made a lot of work for this conjecture [9, 10] and then confirmed this conjecture [11].

However, Bollob$\acute{a}$s and Scott gave the following theorem which not only implies Conjecture 1 for regular graphs(every vertex has the same degree) but also reduces the upper bound e(G) / 3 to e(G) / 4.

Theorem 1

[3] Let $d \ge 2$ be an integer and G a d-regular graph. Then V(G) admits a balanced bipartition $V_{1},V_{2}$ such that

(1) :

$\max \{e(V_{1}),e(V_{2})\}\le \frac{1}{4}((d-1)/d)e(G)$ when d is odd,

(2) :

$\max \{e(V_{1}),e(V_{2})\}\le \frac{1}{4}(d/(d+1))e(G)$ when d is even and |V(G)| is even, and

(3) :

$\max \{e(V_{1}),e(V_{2})\}\le \frac{1}{4}(d/(d+1))e(G)+d/4$ when d is even and |V(G)| is odd.

Yan and Xu [12] generalized Theorem 1 to graphs with $\varDelta (G)-\delta (G) = 1$ as the following theorem shows.

Theorem 2

[12] Let $d \ge 2$ be an integer and G a graph with $n_{1}$ vertices of degree d and $n_{2}= |V(G)|-n_{1}$ vertices of degree $d-1$. Then V(G) admits a balanced bipartition $V_{1},V_{2}$ such that

(1) :

$\max \{e(V_{1}),e(V_{2})\}\le e(G)/4-n_{1}/8$ when d is odd and |V(G)| is even,

(2) :

$\max \{e(V_{1}),e(V_{2})\}\le e(G)/4-n_{1}/8+(d-1)/8$ when d is odd and |V(G)| is odd,

(3) :

$\max \{e(V_{1}),e(V_{2})\}\le e(G)/4+n_{2}/8$ when d is even and |V(G)| is even, and

(4) :

$\max \{e(V_{1}),e(V_{2})\}\le e(G)/4+n_{2}/8+d/8$ when d is even and |V(G)| is odd.

Furthermore, in [5], Hu, He and Hao extended Yan’s result to graphs with $\varDelta (G)-\delta (G) = 2$.

Theorem 3

[5] Let $d \ge 2$ be an integer and G a graph with $n_{1}$ vertices of degree $d-1$, $n_{2}$ vertices of degree d and $n_{3}$ vertices of degree $d+1$. Then V(G) admits a balanced bipartition $V_{1},V_{2}$ such that

(1) :

$\max \{e(V_{1}),e(V_{2})\}\le e(G)/4-(n_{2}+2n_{3})/8+\alpha /2$ when |V(G)| is even and d is odd,

(2) :

$\max \{e(V_{1}),e(V_{2})\}\le e(G)/4-(n_{2}+2n_{3})/8+\alpha /2+(d-1)/8$ when |V(G)| is odd and d is odd,

(3) :

$\max \{e(V_{1}),e(V_{2})\}\le e(G)/4+(n_{1}-n_{3})/8+\alpha /2$ when |V(G)| is even and d is even, and

(4) :

$\max \{e(V_{1}),e(V_{2})\}\le e(G)/4+(n_{1}-n_{3})/8+\alpha /2+d/8$ when |V(G)| is odd and d is even, where

$$\begin{aligned} \alpha =\left\{ \begin{array}{ll} n_{13}, &{} \hbox {if}~ \max e\{(V_{1}),e(V_{2})\} = e(V_{1}), \\ n_{23}, &{} \hbox {if}~ \max e\{(V_{1}),e(V_{2})\} = e(V_{2}). \end{array} \right. \end{aligned}$$

Here, $n_{i3}$ denotes the number of vertices in $V_{i}$ with degree $d+1$, $1\le i \le 2$.

In this paper, we further generalize the result in [5] to general graphs with the following theorem. For convenience, let $\varDelta (G)=\varDelta$, $\delta (G)=\delta$ and $N_{G}(u)=N(u)$.

Theorem 4

Let G be a graph with n vertices and m edges. Suppose that $\varDelta -\delta =t-1, t\ge 2$ and $n_{i}$ is the number of vertices in G with degree $\delta +i-1, 1 \le i \le t$. Then G has a balanced bipartition $V_{1}, V_{2}$, such that

(1) :

$\max \{e(V_{1}),e(V_{2})\} \le \frac{m}{4}-\frac{\sum _{i=2}^{t}(i-1)n_{i}}{8}+\frac{\alpha }{2}$ when n is even and $\delta$ is even,

(2) :

$\max \{e(V_{1}),e(V_{2})\} \le \frac{m}{4}-\frac{\sum _{i=2}^{t}(i-1)n_{i}}{8}+\frac{\alpha }{2} +\frac{\delta }{8}$ when n is odd and $\delta$ is even,

(3) :

$\max \{e(V_{1}),e(V_{2})\} \le \frac{m}{4}+\frac{n_{1}- \sum _{i=3}^{t}(i-2)n_{i}}{8}+\frac{\alpha }{2}$ when n is even and $\delta$ is odd, and

(4) :

$\max \{e(V_{1}),e(V_{2})\} \le \frac{m}{4}+\frac{n_{1}- \sum _{i=3}^{t}(i-2)n_{i}}{8}+\frac{\alpha }{2}+\frac{\delta +1}{8}$ when n is odd and $\delta$ is odd,

where

$$\begin{aligned} \alpha =\left\{ \begin{array}{ll} \sum \limits _{i=3}^{t}(i-2)n_{1,i}, &{} \hbox {if}~\max \{e(V_{1}),e(V_{2})\} = e(V_{1}), \\ \sum \limits _{i=3}^{t}(i-2)n_{2,i}, &{} \hbox {if}~ \max \{e(V_{1}),e(V_{2})\} = e(V_{2}), \end{array} \right. \end{aligned}$$

and $n_{j,i}$ is the number of vertices in $V_{j}$ with degree $\delta +i -1$, $1\le j \le 2$ and $1 \le i \le t$.

It is important to note that Theorem 4 is equivalent to Theorem 2 (resp. 3) when $t=2$(resp. $t=3$).

2 Proof of Theorem 4

In this section, we shall give a proof of Theorem 4. As described in this theorem, there are four cases to be handed. For the sake of clarity, we divide the proof into four parts.

Suppose $V_{1}, V_{2}$ is a balanced bipartition of V(G) with $e(V_{1},V_{2})$ maximum among such partitions. Assume, without loss of generality, that $e(V_{1})\ge e(V_{2})$ and $t= 2k$ is even, since the other cases could be handled by the same way.

Part 1. n is even and $\delta$ is even.

Since n is even, $|V_{1}|=|V_{2}|=\frac{n}{2}$. We consider the following cases.

Case 1.1

$|N(v)\cap V_{1}|\le |N(v)\cap V_{2}|$ for all $v\in V_{1}$.

In this case,

$$\begin{aligned} 2 e(V_{1})\le & {} \frac{\delta }{2}n_{1,1}+\frac{(\delta +1)-1}{2}n_{1,2}+\frac{\delta +2}{2}n_{1,3}+\frac{(\delta +3)-1}{2}n_{1,4}+\cdots \\&+\frac{\delta +(2k-2)}{2}n_{1,2k-1}+\frac{\delta +(2k-1)-1}{2}n_{1,2k}\\= & {} \frac{\delta }{2}\cdot \frac{n}{2} + (n_{1,3}+n_{1,4})+2(n_{1,5}+n_{1,6})+\cdots +(k-1)(n_{1,2k-1}+n_{1,2k}). \end{aligned}$$

It follows that

$$\begin{aligned} e(V_{1}) \le \frac{\delta }{4}\cdot \frac{n}{2}+\frac{\sum _{j=2}^{k}(j-1)(n_{1,2j-1}+n_{1,2j})}{2}. \end{aligned}$$

(1)

By Handshaking Lemma,

$$\begin{aligned} 2m= & {} \delta \cdot n_{1}+(\delta +1)\cdot n_{2}+\cdots +(\delta +2k-1)\cdot n_{2k}\nonumber \\= & {} \delta \cdot n+n_{2}+2n_{3}+\cdots +(2k-1)n_{2k}\nonumber \\= & {} \delta \cdot n+\sum _{j=2}^{2k}(j-1)n_{j}. \end{aligned}$$

(2)

According to Eqs. (1) and (2), we obtain that

$$\begin{aligned} \begin{aligned} e(V_{1})&\le \frac{2m-\sum _{j=2}^{2k}(j-1)n_{j}}{8}+\frac{\sum _{j=2}^{k}(j-1)(n_{1,2j-1}+n_{1,2j})}{2}\\&\le \frac{m}{4}-\frac{\sum _{j=2}^{2k}(j-1)n_{j}}{8}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}. \end{aligned} \end{aligned}$$

Case 1.2

There is a vertex $v_{1}$ in $V_{1}$ such that $|N(v_{1})\cap V_{1}|> |N(v_{1})\cap V_{2}|$.

We first assert that for all $w \in V_{2}$,

$$\begin{aligned} |N(w)\cap V_{2} | < |N(w)\cap V_{1}|. \end{aligned}$$

(3)

Suppose, to the contrary, that there is $v_{2} \in V_{2}$ such that $|N(v_{2})\cap V_{2}|\ge |N(v_{2})\cap V_{1}|$. Then, let $V^{'}_{1}=(V_{1} \backslash \{v_{1}\})\cup \{v_{2}\}, V^{'}_{2}=(V_{2} \backslash \{v_{2}\})\cup \{v_{1}\}$. We get a balanced bipartition $V^{'}_{1}, V^{'}_{2}$ of V(G) with

$$\begin{aligned} \begin{aligned} e(V^{'}_{1},V^{'}_{2})&\ge e(V_{1},V_{2})+(|N(v_{1})\cap V_{1}|-|N(v_{1})\cap V_{2}|)\\&\quad +(|N(v_{2})\cap V_{2}|-|N(v_{2})\cap V_{1}|) \\&\ge e(V_{1},V_{2})+1 \end{aligned} \end{aligned}$$

This is a contradiction to the maximality of $e(V_{1},V_{2})$. Next, using Eq. (3), we deduce that

$$\begin{aligned} \begin{aligned} 2 e(V_{2})&\le \frac{\delta -2}{2}n_{2,1}+\frac{(\delta +1)-1}{2}n_{2,2}+\frac{(\delta +2)-2}{2}n_{2,3}+\cdots \\ {}&\ \ \ \ +\frac{\delta +(2k-2)-2}{2}n_{1,2k-1}+\frac{\delta +(2k-1)-1}{2}n_{1,2k}\\&=\frac{\delta }{2}\cdot \frac{n}{2}-n_{2,1}+ (n_{2,4}+n_{2,5})+2(n_{2,6}+n_{2,7})+\cdots +(k-1)n_{2,2k}, \end{aligned} \end{aligned}$$

which yields that

$$\begin{aligned} e(V_{2})\le \frac{\delta }{4}\cdot \frac{n}{2}- \frac{n_{2,1}}{2}+\frac{\sum _{j=3}^{k}(j-2)(n_{2,2j-2}+n_{2,2j-1})+(k-1)n_{2,2k}}{2}. \end{aligned}$$

(4)

Based on Handshaking Lemma,

$$\begin{aligned} 2e(V_{1})+ & {} e(V_{1},V_{2})=\delta n_{1,1}+(\delta +1)n_{1,2}+ \cdots +(\delta +2k-1)n_{1,2k}\nonumber \\= & {} (\delta +1)|V_{1}|+n_{1,3}+2n_{1,4}+\cdots +(2k-2)n_{1,2k}-n_{1,1}; \end{aligned}$$

(5)

$$\begin{aligned} 2e(V_{2})+ & {} e(V_{1},V_{2})=\delta n_{2,1}+(\delta +1)n_{2,2}+ \cdots +(\delta +2k-1)n_{2,2k}\nonumber \\= & {} (\delta +1)|V_{2}|+n_{2,3}+2n_{2,4}+\cdots +(2k-2)n_{2,2k}-n_{2,1}. \end{aligned}$$

(6)

Thereby,

$$\begin{aligned} e(V_{1})-e(V_{2})=\frac{\left( \sum _{j=3}^{2k}(j-2)n_{1,j}-n_{1,1}\right) -\left( \sum _{j=3}^{2k}(j-2)n_{2,j}-n_{2,1}\right) }{2}. \end{aligned}$$

(7)

Combining Eqs. (2), (4) and (7), we obtain that

$$\begin{aligned} \begin{aligned} e(V_{1})&=e(V_{2})+ \frac{\left( \sum _{j=3}^{2k}(j-2)n_{1,j}-n_{1,1}\right) -\left( \sum _{j=3}^{2k}(j-2)n_{2,j}-n_{2,1}\right) }{2}\\&\le \frac{\delta }{4}\cdot \frac{n}{2}-\frac{n_{2,1}}{2}+\frac{\sum _{j=3}^{k}(j-2)(n_{2,2j-2}+n_{2,2j-1})+(k-1)n_{2,2k}}{2}\\&\quad +\frac{\left( \sum _{j=3}^{2k}(j-2)n_{1,j}-n_{1,1}\right) -\left( \sum _{j=3}^{2k}(j-2)n_{2,j}-n_{2,1}\right) }{2}\\&=\frac{\delta }{4}\cdot \frac{n}{2}\!+\!\frac{\sum _{j\!=\!3}^{k}(j\!-\!2)(n_{2,2j\!-\!2}\!+\!n_{2,2j\!-\!1})\!+\!(k-1)n_{2,2k}-\sum _{j=3}^{2k}(j-2)n_{2,j}}{2}\\&\quad +\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}-n_{1,1}}{2}\\&\le \frac{\delta }{4}\cdot \frac{n}{2}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}\\&=\frac{m}{4}-\frac{\sum _{j=2}^{2k}(j-1)n_{j}}{8}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}. \end{aligned} \end{aligned}$$

Part 2. n is odd and $\delta$ is even.

We distinguish this part into the following two cases.

Case 2.1

$|V_{1}|=\frac{n+1}{2}, |V_{2}|=\frac{n-1}{2}$.

It is claimed that for all $v \in V_{1}$, $|N(v)\cap V_{1}|\le |N(v)\cap V_{2}|$. On the contrary, assume that there is a vertex $v_{1}\in V_{1}$ such that $|N(v_{1})\cap V_{1}|> |N(v_{1})\cap V_{2}|$. Then, we could increase the size of the partition by moving $v_{1}$ from $V_{1}$ to $V_{2}$. This is a contradiction to the maximality of $e(V_{1},V_{2})$. Therefore,

$$\begin{aligned} \begin{aligned} 2 e(V_{1})&\le \frac{\delta }{2}n_{1,1}+\frac{(\delta +1)-1}{2}n_{1,2}+\frac{\delta +2}{2}n_{1,3}+\cdots \\&\ \ \ +\frac{\delta +(2k-2)}{2}n_{1,2k-1}+\frac{\delta +(2k-1)-1}{2}n_{1,2k}\\&=\frac{\delta }{2}\cdot \frac{n+1}{2} + (n_{1,3}+n_{1,4})+\cdots +(k-1)(n_{1,2k-1}+n_{1,2k}), \end{aligned} \end{aligned}$$

which implies that

$$\begin{aligned} \begin{aligned} e(V_{1})&\le \frac{\delta }{4}\cdot \frac{n+1}{2}+\frac{\sum _{j=2}^{k}(j-1)(n_{1,2j-1}+n_{1,2j})}{2}\\&= \frac{2m-\sum _{j=2}^{2k}(j-1)n_{j}}{8}+\frac{\sum _{j=2}^{k}(j-1)(n_{1,2j-1}+n_{1,2j})}{2}+\frac{\delta }{8}\\&\le \frac{m}{4}-\frac{\sum _{j=2}^{2k}(j-1)n_{j}}{8}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}+\frac{\delta }{8}. \end{aligned} \end{aligned}$$

Case 2.2

$|V_{1}|=\frac{n-1}{2}, |V_{2}|=\frac{n+1}{2}$.

If there is a vertex $v^{\prime }_{2} \in V_{2}$ such that $|N(v^{\prime }_{2})\cap V_{1}|= |N(v^{\prime }_{2})\cap V_{2}|$, then we set $V^{'}_{1}=V_{1}\cup \{v^{\prime }_{2}\}$ and $V^{'}_{2}=V_{2}\backslash \{v^{\prime }_{2}\}$. Thus, we get a balanced bipartition as depicted in Case 2.1.

Now, we assume that $|N(w)\cap V_{1} | \ne |N(w)\cap V_{2}|$ for all $w\in V_{2}$. In fact, $|N(w)\cap V_{1} | >|N(w)\cap V_{2}|$, for all $w \in V_{2}$. Otherwise, there is a vertex $v_{2} \in V_{2}$ such that $|N(v_{2})\cap V_{1}|< |N(v_{2})\cap V_{2}|$. Then, we could increase the size of the partition by moving $v_{2}$ from $V_{2}$ to $V_{1}$. So,

$$\begin{aligned} e(V_{2})\le \frac{\delta }{4}\cdot \frac{n+1}{2}-\frac{n_{2,1}}{2}+ \frac{\sum _{j=3}^{k}(j-2)(n_{2,2j-2}+n_{2,2j-1})+(k-1)n_{2,2k}}{2}. \end{aligned}$$

(8)

Again, by Eqs. (5) and (6), we have that

$$\begin{aligned} e(V_{1})\!-\!e(V_{2})\!=\!\frac{\left( \sum _{j\!=\!3}^{2k}(j\!-\!2)n_{1,j}\!-\!n_{1,1}\right) \!-\!\left( \sum _{j\!=\!3}^{2k}(j-2)n_{2,j}-n_{2,1}\right) }{2} -\frac{\delta +1}{2}. \end{aligned}$$

(9)

By making use of Eqs. (2), (8) and (9), we have

$$\begin{aligned} \begin{aligned} e(V_{1})&\!=\!e(V_{2})\!+\! \frac{\left( \sum _{j\!=\!3}^{2k}(j-2)n_{1,j}-n_{1,1}\right) -\left( \sum _{j=3}^{2k}(j-2)n_{2,j}-n_{2,1}\right) }{2}-\frac{\delta +1}{2}\\&\le \frac{\delta }{4}\cdot \frac{n+1}{2}-\frac{n_{2,1}}{2}+\frac{\sum _{j=3}^{k}(j-2)(n_{2,2j-2}+n_{2,2j-1})+(k-1)n_{2,2k}}{2}\\&\quad +\frac{\left( \sum _{j=3}^{2k}(j-2)n_{1,j}-n_{1,1}\right) -\left( \sum _{j=3}^{2k}(j-2)n_{2,j}-n_{2,1}\right) }{2}-\frac{\delta +1}{2}\\&\le \frac{\delta }{4}\cdot \frac{n+1}{2}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}\\&=\frac{m}{4}-\frac{\sum _{j=2}^{2k}(j-1)n_{j}}{8}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}+\frac{\delta }{8}. \end{aligned} \end{aligned}$$

Part 3. n is even and $\delta$ is odd.

We notice that $|V_{1}|=\frac{n}{2}$, $|V_{2}|=\frac{n}{2}$ since n is even. Also, there are two cases to be treated.

Case 3.1

$|N(v)\cap V_{1}|< |N(v)\cap V_{2}|$ for all $v\in V_{1}$.

Under this case,

$$\begin{aligned} \begin{aligned} 2 e(V_{1})&\le \frac{\delta -1}{2}n_{1,1}+\frac{(\delta +1)-2}{2}n_{1,2}+\frac{(\delta +2)-1 }{2}n_{1,3}+\cdots \\&\quad +\frac{\delta +(2k-2)-1}{2}n_{1,2k-1}+\frac{\delta +(2k-1)-2}{2}n_{1,2k}\\&=\frac{\delta -1}{2}\cdot \frac{n}{2} + (n_{1,3}+n_{1,4})+2(n_{1,5}+n_{1,6})+\cdots \\&\quad +(k-1)(n_{1,2k-1}+n_{1,2k})\\&\le \frac{\delta -1}{4}\cdot \frac{n}{2}+\frac{\sum _{j=2}^{k}(j-1)(n_{1,2j-1}+n_{1,2j})}{2}\\&\le \frac{\delta +1-2}{4}\cdot \frac{n}{2}+\frac{\sum _{j=2}^{k}(j-1)(n_{1,2j-1}+n_{1,2j})}{2}. \end{aligned} \end{aligned}$$

In addition,

$$\begin{aligned} 2m= & {} \delta \cdot n_{1}+(\delta +1)\cdot n_{2}+\cdots +(\delta +2k-1)\cdot n_{2k}\nonumber \\= & {} (\delta +1)\cdot n+n_{3}+\cdots +(2k-2)n_{2k}-n_{1}\nonumber \\= & {} (\delta +1)\cdot n+\sum _{j=2}^{2k}(j-2)n_{j}-n_{1}. \end{aligned}$$

(10)

Thus,

$$\begin{aligned} e(V_{1})\le \frac{m}{4}-\frac{\sum _{j=3}^{2k}(j-2)n_{j}-n_{1}}{8}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}. \end{aligned}$$

Case 3.2

There is a vertex $v_{1} \in V_{1}$ such that $|N(v_{1})\cap V_{1}|\ge |N(v_{1})\cap V_{2}|$.

By an argument similar to Case 1.2, we obtain that for all $w \in V_{2}$,

$$\begin{aligned} |N(w)\cap V_{1}| \ge |N(w)\cap V_{2}|. \end{aligned}$$

(11)

By Eq. (11),

$$\begin{aligned} 2e(V_{2})\le & {} \frac{\delta -1}{2}n_{2,1}+\frac{\delta +1}{2}n_{2,2}+\frac{(\delta +2)-1}{2}n_{2,3}+ \frac{\delta +3}{2}n_{2,4}\\&+\cdots +\frac{\delta +(2k-2)-1}{2}n_{2,2k-1}+\frac{\delta +(2k-1)}{2}n_{2,2k}\\= & {} \frac{\delta +1}{2}\frac{n}{2}-n_{2,1}+\cdots +(k-2)(n_{2,2k-2}+n_{2,2k-1})+(k-1)n_{2,2k}. \end{aligned}$$

As a consequence,

$$\begin{aligned} e(V_{2})\le \frac{\delta +1}{4}\cdot \frac{n}{2}- \frac{n_{2,1}}{2}+\frac{\sum _{j=3}^{k}(j-2)(n_{2,2j-2}+n_{2,2j-1})+(k-1)n_{2,2k}}{2}. \end{aligned}$$

(12)

With the aid of Eqs. (7), (10) and (12), we obtain that

$$\begin{aligned} \begin{aligned} e(V_{1})&=e(V_{2})+ \frac{\left( \sum _{j=3}^{2k}(j-2)n_{1,j}-n_{1,1}\right) -\left( \sum _{j=3}^{2k}(j-2)n_{2,j}-n_{2,1}\right) }{2}\\&\le \frac{\delta +1}{4}\cdot \frac{n}{2}-\frac{n_{2,1}}{2}+\frac{\sum _{j=3}^{k}(j-2)(n_{2,2j-2}+n_{2,2j-1})+(k-1)n_{2,2k}}{2}\\&\quad +\frac{\left( \sum _{j=3}^{2k}(j-2)n_{1,j}-n_{1,1}\right) -\left( \sum _{j=3}^{2k}(j-2)n_{2,j}-n_{2,1}\right) }{2}\\&\le \frac{\delta +1}{4}\cdot \frac{n}{2}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}\\&=\frac{m}{4}-\frac{\sum _{j=3}^{2k}(j-2)n_{j}-n_{1}}{8}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}. \end{aligned} \end{aligned}$$

Part 4. n is odd and $\delta$ is odd.

Similarly, we consider the following two cases.

Case 4.1

$|V_{1}|=\frac{n+1}{2}$ and $|V_{2}|=\frac{n-1}{2}$.

According to the discussion of Case 2.1, we claim that $|N(v)\cap V_{1}|\le |N(v)\cap V_{2}|$ for all $v\in V_{1}$. Therefore,

$$\begin{aligned} \begin{aligned} 2 e(V_{1})&\le \frac{\delta -1}{2}n_{1,1}+\frac{\delta +1}{2}n_{1,2}+\frac{(\delta +2)-1}{2}n_{1,3}+\cdots \\&\ \ \ +\frac{\delta +(2k-2)-1}{2}n_{1,2k-1}+\frac{\delta +(2k-1)}{2}n_{1,2k}\\&=\frac{\delta +1}{2}\cdot \frac{n+1}{2} -n_{1,1}+ (n_{1,4}+n_{1,5})+\cdots \\&\ \ \ +(k-2)(n_{1,2k-2}+n_{1,2k-1})+(k-1)n_{1,2k}. \end{aligned} \end{aligned}$$

It follows that

$$\begin{aligned} \begin{aligned} e(V_{1})&\le \frac{\delta +1}{4}\cdot \frac{n+1}{2}+\frac{\sum _{j=3}^{k}(j-2)(n_{1,2j-2}+n_{1,2j-1})+(k-1)n_{1,2k}-n_{1,1}}{2}\\&\le \frac{m}{4}-\frac{\sum _{j=3}^{2k}(j-2)n_{j}-n_{1}}{8}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}+\frac{\delta +1}{8}. \end{aligned} \end{aligned}$$

Case 4.2

$|V_{1}|=\frac{n-1}{2}$ and $|V_{2}|=\frac{n+1}{2}$.

A similar argument to Case 2.2 deduces that for all $w \in V_{2}$

$$\begin{aligned} |N(w)\cap V_{1} | \ge |N(w)\cap V_{2}|. \end{aligned}$$

Therefore,

$$\begin{aligned} e(V_{2})\le \frac{\delta +1}{4}\cdot \frac{n+1}{2}- \frac{n_{2,1}}{2}+\frac{\sum _{j=3}^{k}(j-2)(n_{2,2j-2}+n_{2,2j-1})+(k-1)n_{2,2k}}{2}, \end{aligned}$$

which combining Eqs. (9) and (10) imply that

$$\begin{aligned} \begin{aligned} e(V_{1})&=e(V_{2})+ \frac{\left( \sum _{j=3}^{2k}(j-2)n_{1,j}-n_{1,1}\right) -\left( \sum _{j=3}^{2k}(j-2)n_{2,j}-n_{2,1}\right) }{2}-\frac{\delta +1}{2}\\&\le \frac{\delta +1}{4}\cdot \frac{n+1}{2}-\frac{n_{2,1}}{2}+\frac{\sum _{j=3}^{k}(j-2)(n_{2,2j-2}+n_{2,2j-1})+(k-1)n_{2,2k}}{2}\\&\quad +\frac{\left( \sum _{j=3}^{2k}(j-2)n_{1,j}-n_{1,1}\right) -\left( \sum _{j=3}^{2k}(j-2)n_{2,j}-n_{2,1}\right) }{2}-\frac{\delta +1}{2}\\&\le \frac{\delta +1}{4}\cdot \frac{n+1}{2}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}\\&=\frac{m}{4}-\frac{\sum _{j=3}^{2k}(j-2)n_{j}-n_{1}}{8}+\frac{\sum _{j=3}^{2k}(j-2)n_{1,j}}{2}+\frac{\delta +1}{8}. \end{aligned} \end{aligned}$$

Here, we establish the 4 Parts. Consequently, the proof of Theorem 4 is finished.