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)$。

如果图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)}$。

猜想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

参考文献