一些图的弱外部平衡划分

Weak External Bisection of Some Graphs

摘要: 设G是一个图。G的一个2-划分是V(G)的一个2-划分，即V(G)=V₁∪V₂且V₁∩V₂= ∅。如果一个2-划分满足||V₁|-|V₂||≤1，我们就称其为平衡划分。本文的研究主要基于Bollobás和Scott提出的一个猜想：每个图G都有一个平衡划分(V₁,V₂)，对于V₁中的每一个顶点v，v的邻点中至少有一半减去一个在V₂中；对于V₂中的每一个顶点v，v的邻点中至少有一半减去一个在V₁中。在本文中，将对二部图、皇冠图以及风车图证实这一猜想。

Abstract: Let G be a graph. A bipartition of G is a bipartition of V(G) with V(G)=V₁∪V₂ and V₁∩V₂= ∅. If a bipartition satisfies ||V₁|-|V₂||≤1, we call it a bisection. The research in this paper is mainly based on a conjecture proposed by Bollobás and Scott: every graph G has a bisection (V₁,V₂) such that ∀v∈V₁, at least half minus one of the neighbors of v are in the V₂;∀v∈V₂, at least half minus one of the neighbors of v are in the V1. In this paper, we confirm this conjecture for some bipartite graphs, crown graphs and windmill graphs.

1. 引言

设图G的顶点集为 $V\left(G\right)$ ，边集为 $E\left(G\right)$ 。G的外部划分是 $V\left(G\right)=V_1\cup V_2$ 且 $V_1\cap V_2=\varnothing$ ，并且满足对于V₁中的每一个顶点v，v的邻点中至少有一半在V₂中；对于V₂中的每一个顶点v，v的邻点中至少有一半在V₁中。Shelah和Milner [1] 发现了不存在外部划分的不可数图，并证明了每个图都有一个外部3-划分；并且他们还提出了一个猜想：任何可数图都有一个外部划分。Aharoni，Milner和Prikry [2] 证明了有限个无穷度顶点的图存在一个外部划分。Fiorini和Silva [3] 发现Shelah和Milner [1] 给出的反例中的图没有一个顶点是有限次的，因此他们开始寻找具有此性质且不存在外部划分的图的最小基数。

如果G的一个2-划分满足 $|\left|V_1\right|-\left|V_2\right||\le 1$ ，我们就称它为G的一个平衡划分，并记作 $\left(V_1,V_2\right)$ 。Ban和Linial [4] 发现，每一个1、3或4类正则图G都有一个外部平衡划分。Bollobás和Scott [5] 发现，并非每个图都有外部平衡划分，他们给出了一个反例，当 $m\ge 2l+3$ 时 $K_{2l+1,m}$ 没有外部平衡划分。Esperet、Mazzuoccolo和Tarsi [6] 发现了一组没有外部平衡划分且至少包含2个桥的3-正则图。

对于顶点 $u,v\in V\left(G\right)$ ，如果 $uv\in E\left(G\right)$ ，则称边uv与顶点u和v相关联。v的度是与v关联的边的数目，用 $d\left(v\right)$ 表示。设 $\left(V_1,V_2\right)$ 是G的一个平衡划分。对于V₁中的顶点v，v的内部度是与v关联且另一个端点也在V₁中的边的数目；v的外部度是与v关联且另一个端点在V₂中的边的数目。对于V₂中的顶点v，v的内部度是与v关联且另一个端点也在V₂中的边的数目；v的外部度是与v关联且另一个端点在V₁中的边的数目。为方便写作，将v的内部度记作 $d_{in}\left(v\right)$ ，v的外部度记作 $d_{ex}\left(v\right)$ 。

Figure 1. $G_{3,3}$

图1. $G_{3,3}$

如果图G的顶点集可以划分为两个非空子集X和Y，使得X中任意两个顶点之间没有边相连，Y中任意两个顶点之间没有边相连，则称该图为二部图，记作 $G=\left[X,Y\right]$ 。

皇冠图 [7] $G_{n,m}$ 满足以下条件：

$V\left(G_{n,m}\right)=\left\{u_i|i=1,2,\cdots ,n\right\}\cup \left\{v_i|i=1,2,\cdots ,n\right\}\underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j=1,2,\cdots ,m\right\}$ ；

$\begin{array}{l}E\left(G_{n,m}\right)=\left\{u_1{u}_2,u_2{u}_3,\cdots ,u_n{u}_1\right\}\cup \left\{v_1{v}_2,v_2{v}_3,\cdots ,v_n{v}_1\right\}\cup \left\{v_1{u}_1,v_2{u}_2,\cdots ,v_n{u}_n\right\}\\ \underset{i=1}{\overset{n}{\cup }}\left\{u_i{u}_{ij}|j=1,2,\cdots ,m\right\}\underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}{u}_{i\left(j+1\right)}|j=1,2,\cdots ,m-1\right\},\left(n\ge 3,m\ge 1\right).\end{array}$

例如，图1展示了 $m=3,n=3$ 时的皇冠图 $G_{3,3}$ 。

风车图 $K_m^{\left(n\right)}$ 是由n个具有一个共同顶点的m阶完全图 $K_m$ 组成的图。

例如，图2展示了 $m=4$ 时的风车图 $K_4^{\left(n\right)}$ 。

Figure 2. $K_4^{(\; n\; )}$

图2. $K_4^{(\; n\; )}$

猜想1.1 (Bollobás and Scott [5] )每个图G都有一个弱外部平衡划分，即G有一个平衡划分 $\left(V_1,V_2\right)$ 使得

$d_{ex}\left(v\right)\ge d_{in}\left(v\right)-1$ $\forall v\in V\left(G\right)$ .

Ji、Ma、Yan和Yu [8] 证明了每个图形序列对于猜想1.1的成立都有一个实现。在同一篇文章中，他们也给出了猜想1.1的无穷反例族。

在本文中，我们通过展示以下三个定理，证实猜想1.1对部分图成立。

定理1.1 $G\left[X,Y\right]$ 是 $\left|X\right|=3,\left|Y\right|=n$ 的二部图，则 $G\left[X,Y\right]$ 有弱外部平衡划分。

定理1.2 每一个皇冠图 $G_{n,m}$ 都有弱外部平衡划分。

定理1.3 每一个风车图 $K_m^{\left(n\right)}$ 都有弱外部平衡划分。

事实上，通过定理1.2的证明，可得到皇冠图 $G_{n,m}$ 具有更强的结果，每一个皇冠图 $G_{n,m}$ 都有外部平衡划分。

2. 弱外部平衡划分

在本节中，我们将证明定理1.1、定理1.2和定理1.3。

定理1.1的证明设 $G=\left[X,Y\right]$ 是一个二部图，顶点集有X和Y两部分，我们定义 $Y_S=\left\{y\in Y|N\left(y\right)=S,S\subseteq X\right\}$ 。对于集合S，我们定义函数

$f\left(S\right)=\{\begin{array}{l}1如果\left|S\right|是奇数\text{;}\\ 0如果\left|S\right|是偶数\text{.}\end{array}$ (1)

令 $X=\left\{v_1,v_2,v_3\right\}$ ，在不失一般性的前提下，假设

$\left|Y_{\left\{v_1,v_3\right\}}\right|\ge \left|Y_{\left\{v_1,v_2\right\}}\right|\ge \left|Y_{\left\{v_2,v_3\right\}}\right|$ .

否则，我们可以对X中的三个顶点重新标注。我们通过三个步骤给出 $V\left(G\right)$ 的一个弱外部平衡划分 $\left(V_1,V_2\right)$ 。

首先，令 $\left\{v_1,v_2\right\}\subseteq V_1$ ， $\left\{v_3\right\}\subseteq V_2$ ， $Y_{\left\{v_1,v_2\right\}}\subseteq V_2$ 和 $Y_{\left\{v_1,v_3\right\}}^{*}\subseteq V_1$ 。这里 $Y_{\left\{v_1,v_3\right\}}^{*}\subseteq Y_{\left\{v_1,v_3\right\}}$ ， $\left|Y_{\left\{v_1,v_3\right\}}^{*}\right|=\left|Y_{\left\{v_1,v_2\right\}}\right|$ 。由于 $\left|Y_{\left\{v_1,v_3\right\}}\right|\ge \left|Y_{\left\{v_1,v_2\right\}}\right|$ ，因而 $Y_{\left\{v_1,v_3\right\}}^{*}$ 是存在的。令 $Y_{\left\{v_1,v_3\right\}}^{**}=Y_{\left\{v_1,v_3\right\}}\backslash Y_{\left\{v_1,v_3\right\}}^{*}$ 。

其次，我们依次划分集合 $Y_{\left\{v_2\right\}}$ ， $Y_{\left\{v_1\right\}}$ ， $Y_{\left\{v_1,v_3\right\}}^{**}$ ， $Y_{\left\{v_1,v_2,v_3\right\}}$ ， $Y_{\left\{v_2,v_3\right\}}$ 和 $Y_{\left\{v_3\right\}}$ 中的奇数集。将集合 $Y_{\left\{v_2\right\}}$ ， $Y_{\left\{v_1\right\}}$ ， $Y_{\left\{v_1,v_3\right\}}^{**}$ ， $Y_{\left\{v_1,v_2,v_3\right\}}$ ， $Y_{\left\{v_2,v_3\right\}}$ 和 $Y_{\left\{v_3\right\}}$ 中的奇数集依次记作 $S_1,S_2,\cdots ,S_m$ 。对于每个 $i\in \left\{1,\cdots ,m\right\}$ ，如果i是奇数，则将 $S_i$ 中的 $\lceil \frac{\left|S_i\right|}{2}\rceil$ 个点放入V₂中且将其余下的 $\lfloor \frac{\left|S_i\right|}{2}\rfloor$ 个点放入V₁中；如果i是偶数，则将 $S_i$ 中的 $\lceil \frac{\left|S_i\right|}{2}\rceil$ 个点放入V₁中且将其余下的 $\lfloor \frac{\left|S_i\right|}{2}\rfloor$ 个点放入V₂中。

最后，将集合 $Y_{\left\{v_2\right\}}$ ， $Y_{\left\{v_1\right\}}$ ， $Y_{\left\{v_1,v_3\right\}}^{**}$ ， $Y_{\left\{v_1,v_2,v_3\right\}}$ ， $Y_{\left\{v_2,v_3\right\}}$ 和 $Y_{\left\{v_3\right\}}$ 中的偶数集依次记作 $T_1,T_2,\cdots ,T_k$ 。对于每个 $i\in \left\{1,\cdots ,k\right\}$ ，将 $T_i$ 中的 $\frac{\left|T_i\right|}{2}$ 个点放入V₁中且将其余下的 $\frac{\left|T_i\right|}{2}$ 个点放入V₂中。

现在，我们来证明V₁和V₂构成了 $G\left[X,Y\right]$ 的一个弱外部平衡划分。显然，如果m是奇数，则 $\left|V_1\right|-\left|V_2\right|=0$ ；如果m是偶数，则 $\left|V_1\right|-\left|V_2\right|=1$ 。所以 $\left(V_1,V_2\right)$ 是一个平衡划分。因为 $\left\{v_1,v_2\right\}\subseteq V_1$ 和 $Y_{\left\{v_1,v_2\right\}}\subseteq V_2$ ，则对于每一个点 $v\in Y_{\left\{v_1,v_2\right\}}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=2$ 。此外，如果 $S\subseteq \left\{v_1,v_2,v_3\right\}$ 且 $\left|S\right|=1\text{or}3$ ，则对于每一个点 $v\in Y_S$ ， $\left|d_{ex}\left(v\right)-d_{in}\left(v\right)\right|=1$ ；如果 $S\subseteq \left\{v_1,v_2,v_3\right\}$ ， $S\ne \left\{v_1,v_2\right\}$ 且 $\left|S\right|=2$ ，则对于每一个点 $v\in Y_S$ ， $d_{ex}\left(v\right)=d_{in}\left(v\right)$ 。因此对于每一个点 $v\in Y$ ， $d_{ex}\left(v\right)\ge d_{in}\left(v\right)-1$ 。

令

$\begin{array}{l}{S}_1=\left\{Y_{\left\{v_1\right\}},Y_{\left\{v_1,v_3\right\}}^{**},Y_{\left\{v_1,v_2,v_3\right\}}\right\},\\ S_2=\left\{Y_{\left\{v_1,v_2,v_3\right\}},Y_{\left\{v_2,v_3\right\}}\right\},\\ S_3=\left\{Y_{\left\{v_1,v_3\right\}}^{**},Y_{\left\{v_1,v_2,v_3\right\}},Y_{\left\{v_2,v_3\right\}},Y_{\left\{v_3\right\}}\right\}.\end{array}$

令 ${{\mathcal{S}}^{\prime }}_i=\left\{S_1,S_2,\cdots ,S_m\right\}\cap {\mathcal{S}}_i$ ， $i=1,2,3$ 。注意， $S_1,S_2,\cdots ,S_m$ 是顺次标记集合 $Y_{\left\{v_2\right\}}$ ， $Y_{\left\{v_1\right\}}$ ， $Y_{\left\{v_1,v_3\right\}}^{**}$ ， $Y_{\left\{v_1,v_2,v_3\right\}}$ ， $Y_{\left\{v_2,v_3\right\}}$ 和 $Y_{\left\{v_3\right\}}$ 中的奇数集，则每一个 ${{\mathcal{S}}^{\prime }}_i$ 都包含了多个 $S_1,S_2,\cdots ,S_m$ 的连续集合。令 ${\mathcal{T}}_i=\left\{T_1,T_2,\cdots ,T_k\right\}\cap {\mathcal{S}}_i$ ， $i=1,2,3$ 。我们有

$d_{ex}\left(v_1\right)=\left|Y_{\left\{v_1,v_2\right\}}\right|+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_1\\ i是奇数\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_1\\ i是偶数\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_1}{\sum }\frac{\left|T_i\right|}{2}};$

$d_{in}\left(v_1\right)=\left|Y_{\left\{v_1,v_3\right\}}^{*}\right|+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_1\\ i是奇数\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_1\\ i是偶数\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_1}{\sum }\frac{\left|T_i\right|}{2}}.$

因为 ${{\mathcal{S}}^{\prime }}_i$ 包含了 $S_1,S_2,\cdots ,S_m$ 的连续集合，则有 $\left|d_{ex}\left(v_1\right)-d_{in}\left(v_1\right)\right|=f\left({{\mathcal{S}}^{\prime }}_1\right)$ ，这里 $f\left({{\mathcal{S}}^{\prime }}_1\right)$ 的定义如(1)。易得

$\begin{array}{l}{d}_{ex}\left(v_2\right)=\left|Y_{\left\{v_1,v_2\right\}}\right|+\lceil \frac{\left|Y_{\left\{v_2\right\}}\right|}{2}\rceil +{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_2\\ i是奇数\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_2\\ i是偶数\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_2}{\sum }\frac{\left|T_i\right|}{2}};\\ d_{in}\left(v_2\right)=\lfloor \frac{\left|Y_{\left\{v_2\right\}}\right|}{2}\rfloor +{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_2\\ i是奇数\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_2\\ i是偶数\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_2}{\sum }\frac{\left|T_i\right|}{2}}.\end{array}$

显然，如果 $\left|Y_{\left\{v_2\right\}}\right|$ 是奇数，则 $S_1=Y_{\left\{v_2\right\}}$ 。因此，我们有 $d_{ex}\left(v_2\right)-d_{in}\left(v_2\right)\ge \left|Y_{\left\{v_1,v_2\right\}}\right|+f\left(Y_{\left\{v_2\right\}}\right)-f\left({{\mathcal{S}}^{\prime }}_2\right)\ge -1$ 。类似地，有

$\begin{array}{l}{d}_{ex}\left(v_3\right)=\left|Y_{\left\{v_1,v_3\right\}}^{*}\right|+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_3\\ i是奇数\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_3\\ i是偶数\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_3}{\sum }\frac{\left|T_i\right|}{2}};\\ d_{in}\left(v_3\right)={\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_3\\ i是奇数\end{array}}{\sum }\lceil \frac{\left|S_i\right|}{2}\rceil }+{\displaystyle \underset{\begin{array}{l}{S}_i\subseteq {{\mathcal{S}}^{\prime }}_3\\ i是偶数\end{array}}{\sum }\lfloor \frac{\left|S_i\right|}{2}\rfloor }+{\displaystyle \underset{T_i\subseteq {\mathcal{T}}_3}{\sum }\frac{\left|T_i\right|}{2}}.\end{array}$

所以 $\left|d_{ex}\left(v_3\right)-d_{in}\left(v_3\right)\right|\ge \left|Y_{\left\{v_1,v_3\right\}}^{*}\right|-f\left({{\mathcal{S}}^{\prime }}_2\right)$ 。则对于每一个 $v_i\in X$ ， $d_{ex}\left(v_i\right)\ge d_{in}\left(v_i\right)-1$ 。因此 $\left(V_1,V_2\right)$ 是 $G\left[X,Y\right]$ 的一个弱外部平衡划分。n

定理1.2的证明 令 $V\left(G_{n,m}\right)=\left\{u_i|i=1,\cdots ,n\right\}\cup \left\{v_i|i=1,\cdots ,n\right\}\underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j=1,\cdots ,m\right\}$ 。我们通过两个步骤给出 $V\left(G_{n,m}\right)$ 的一个弱外部平衡划分 $\left(V_1,V_2\right)$ 。

首先，令 $\left\{v_i|i\in \left\{1,2,\cdots ,n\right\}且i是奇数\right\}\subset V_2$ 且 $\left\{v_i|i\in \left\{1,2,\cdots ,n\right\}且i是偶数\right\}\subset V_1$ ； $\left\{u_i|i\in \left\{1,2,\cdots ,n\right\}且i是奇数\right\}\subset V_1$ 且 $\left\{u_i|i\in \left\{1,2,\cdots ,n\right\}且i是偶数\right\}\subset V_2$ 。

其次，我们划分集合 $\underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j=1,2,\cdots ,m\right\}$ 。 $\underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j=1,2,\cdots ,m\right\}$ 的划分依赖于 $\underset{i=1}{\overset{n}{\cup }}\left\{u_i\right\}$ 的划分。对于一个给定的k，如果 $u_k\in V_1$ ，则令 $\left\{u_{kj}|j\in \left\{1,2,\cdots ,m\right\}且j是奇数\right\}\subset V_2$ 且 $\left\{u_{kj}|j\in \left\{1,2,\cdots ,m\right\}且j是偶数\right\}\subset V_1$ ；如果 $u_k\in V_2$ ，则令 $\left\{u_{kj}|j\in \left\{1,2,\cdots ,m\right\}且j是奇数\right\}\subset V_1$ 且 $\left\{u_{kj}|j\in \left\{1,2,\cdots ,m\right\}且j是偶数\right\}\subset V_2$ 。

现在，我们来证明V₁和V₂构成了 $G_{n,m}$ 的一个弱外部平衡划分。显然，如果n和m都为奇数，则 $\left|V_1\right|-\left|V_2\right|=1$ ；否则， $\left|V_1\right|-\left|V_2\right|=0$ 。所以 $\left(V_1,V_2\right)$ 是一个平衡划分。如果n是偶数，则对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{v_i\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ ；如果n是奇数，则 $d_{ex}\left(v_1\right)-d_{in}\left(v_1\right)=1$ ， $d_{ex}\left(v_n\right)-d_{in}\left(v_n\right)=1$ 且对于每一个 $v\in \underset{i=2}{\overset{n-1}{\cup }}\left\{v_i\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ 。所以，在任何情况下， $d_{ex}\left(v_i\right)\ge d_{in}\left(v_i\right),i=1,\cdots ,n$ 。

如果m是奇数，则对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_{i1},u_{im}\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=2$ ；对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j\in \left\{2,\cdots ,m-1\right\}且j是偶数\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=1$ 且对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j\in \left\{2,\cdots ,m-1\right\}且j是奇数\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ 。如果m是偶数，则对于每一个 $d_{ex}\left(u_{i1}\right)-d_{in}\left(u_{i1}\right)=2$ ， $d_{ex}\left(u_{im}\right)=d_{in}\left(u_{im}\right)$ ；对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j\in \left\{2,\cdots ,m-1\right\}且j是偶数\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=1$ 且对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_{ij}|j\in \left\{2,\cdots ,m-1\right\}且j是奇数\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ 。所以，在任何情况下， $d_{ex}\left(u_{ij}\right)\ge d_{in}\left(u_{ij}\right),i=1,\cdots ,n;j=1,\cdots ,m$ 。

如果n和m都是奇数，则 $d_{ex}\left(u_1\right)-d_{in}\left(u_1\right)=2$ ， $d_{ex}\left(u_n\right)-d_{in}\left(u_n\right)=2$ 且对于每一个 $v\in \underset{i=2}{\overset{n-1}{\cup }}\left\{u_i\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=4$ 。如果n是奇数且m是偶数，则 $d_{ex}\left(u_1\right)-d_{in}\left(u_1\right)=1$ ， $d_{ex}\left(u_n\right)-d_{in}\left(u_n\right)=1$ 且对于每一个 $v\in \underset{i=2}{\overset{n-1}{\cup }}\left\{u_i\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ 。如果n是偶数且m是奇数，则对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_i\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=4$ 。如果n和m都是偶数，则对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{u_i\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ 。所以，在任何情况下， $d_{ex}\left(u_i\right)\ge d_{in}\left(u_i\right),i=1,\cdots ,n$ 。因此 $\left(V_1,V_2\right)$ 是 $G_{n,m}$ 的一个弱外部平衡划分。n

定理1.3的证明 仿照图2我们对图 $K_m^{\left(n\right)}$ 的顶点进行标注，得其顶点集为 $V\left(K_m^{\left(n\right)}\right)=\left\{x_0\right\}\underset{i=1}{\overset{n}{\cup }}\left\{x_{i1},x_{i2},\cdots ,x_{i,m-1}\right\}$ 。令 $\left\{x_0\right\}\subset V_1$ 。

我们考虑以下两种情况。

情况1 m是奇数

令 $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}且j是偶数\right\}\subset V_1$ 且 $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}且j是奇数\right\}\subset V_2$ 。此时， $\left|V_1\right|-\left|V_2\right|=1$ 。所以 $\left(V_1,V_2\right)$ 是一个平衡划分。 $d_{ex}\left(x_0\right)-d_{in}\left(x_0\right)=1$ 。对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}且j是偶数\right\}$ ， $d_{ex}\left(v\right)=d_{in}\left(v\right)$ ；对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}且j是奇数\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=2$ 。因此 $\left(V_1,V_2\right)$ 是 $K_m^{\left(n\right)}$ 的一个弱外部平衡划分。

情况2 m是偶数

如果i是奇数，令 $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}且j是奇数\right\}\subset V_2$ 且 $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}且j是偶数\right\}\subset V_1$ ；如果i是偶数，令 $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}且j是奇数\right\}\subset V_1$ 且 $\underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}且j是偶数\right\}\subset V_2$ 。

现在，我们来证明V₁和V₂构成了 $K_m^{\left(n\right)}$ 的一个弱外部平衡划分。显然，如果n是奇数， $\left|V_1\right|-\left|V_2\right|=0$ ；如果n是偶数， $\left|V_1\right|-\left|V_2\right|=1$ 。所以 $\left(V_1,V_2\right)$ 是一个平衡划分。如果i是奇数，则对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\underset{j=1}{\overset{m-1}{\cup }}\left\{x_{ij}\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=1$ ；如果i是偶数，则对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}且j是奇数\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=-1$ 且对于每一个 $v\in \underset{i=1}{\overset{n}{\cup }}\left\{x_{ij}|j\in \left\{1,2,\cdots ,m-1\right\}且j是偶数\right\}$ ， $d_{ex}\left(v\right)-d_{in}\left(v\right)=3$ 。如果n是偶数，则 $d_{ex}\left(x_0\right)=d_{in}\left(x_0\right)$ ；如果n是奇数，则 $d_{ex}\left(x_0\right)-d_{in}\left(x_0\right)=1$ 。因此 $\left(V_1,V_2\right)$ 是 $K_m^{\left(n\right)}$ 的一个弱外部平衡划分。 n