双正则可二部图的反魔幻标号

Antimagic Labeling of Biregular Cobipartite Graph

摘要: 一个简单图G的反魔幻标号是一个双射，使得对于G中任意两点u，v，有 。如果一个图具有反魔幻标号，那么这个图就是反魔幻的。在1990年，Hartsfield和Ringe定义了图的反魔幻标号，并且猜想除K₂以外的每一个连通图都是反魔幻的。此猜想自1990年被提出以来受到广泛关注，但仍未完全解决。本文从完全图入手，设计出一种新的标号方式区分了完全图中的各点并且可以得到各点具体的标号和，并且运用这种标号方式将猜想推广到了一类特殊图上——双正则可二部图，证明了每一个双正则可二部图都是反魔幻的。

Abstract: An antimagic labeling of a simple graph G is a bijection  such that  for any two vertices u, v in G. In 1990, Hartsfield and Ringel defined the antimagic labeling of graphs and every connected graph other than K₂ is antimagic. This conjecture has received a lot of attention since it was proposed in 1990, but it is still not completely solved. In this paper, we start from complete graphs and devise a new labeling method to distinguish the vertices in complete graphs and obtain the specific sum of the labels of each vertex, and use this labeling method to extend the conjecture to a special class of graphs, the biregular cobipartite graphs, and prove that every biregular cobipartite graph is antimagic.

1. 引言

本文所考虑的图都是简单、连通、无向的有限图。

对于一个简单图G，设 $G=\left(V\left(G\right),E\left(G\right)\right)$ 。设m为正整数， $\left|E\left(G\right)\right|=m$ ，图G的标号是图的边集到整数集的一个双射 $\phi :E\left(G\right)\to \left\{1,2,\cdots ,\left|E\left(G\right)\right|\right\}$ 。对于 $V\left(G\right)$ 中的一个顶点v，v的标号和是与顶点v相关联的边的标号之和，用 $\phi \left(v\right)$ 表示。如果对于 $V\left(G\right)$ 中的任意两个不同的顶点u和v，都有 $\phi \left(u\right)\ne \phi \left(v\right)$ ，那么就称G的标号是反魔幻的。如果一个图具有反魔幻标号，我们就称这个图是反魔幻的。

1990年，Hartsfield和Ringel [1] 定义了图的反魔幻标号，并提出了反魔幻标号猜想，他们还给出了一些反魔法图，包括至少有3个顶点的路图、圈图、至少有3个顶点的星图、轮图、完全图等，并在同一篇文章中猜想每棵至少有三个顶点的树图都是反魔幻的。

猜想1. (反魔幻标号猜想 [1] )除K₂以外的每一个连通图都是反魔幻的。

猜想2. ( [1] )除K₂以外的每一个树图都是反魔幻的。

这两个猜想提出后，引起了众多学者的关注并且通过研究得到了许多有趣的反魔幻图。对于树图，Kaplan，Lev Roditty [2] 证明了最多只有一个二度点的树是反魔幻的，Liang，Wong和Zhu [3] 将结果扩展到了有更多二度点的树图上。对于一些特殊类型的树图，在 [4] [5] [6] [7] 中，每个完全m叉树，毛虫图，蜘蛛图，递推的二叉树和斐波那契树都被证明是反魔幻的。在 [8] [9] [10] [11] [12] 中，所有的正则图都被证明是反魔幻的。反魔幻标号猜想其他的部分结果可以在 [13] - [18] 中被找到。

我们称一个二部图 $G=\langle V_1,V_2,E\rangle$ 是双正则的，若同一顶点集中的度也相同；称一个简单图G是可二部的，若其顶点集 $V\left(G\right)$ 存在划分 $X\cup Y$ ，使得X和Y都是团(团是一个两两之间有边的顶点集合，类似于完全图)。对于一个可二部的图G，若其顶点集 $V\left(G\right)$ 划分为X和Y，若 $E\left[X,Y\right]$ 的导出子图是一个双正则二部图，则称图G是一个双正则可二部图。

寻找一个双正则可二部图的反魔幻标号，重点是对中间的双正则二部图以及两端的团的处理。本文从完全图入手，设计出一种新的标号方式区分了完全图的各点并且可以得到各点具体的标号和(具体标号处理方式详见第二部分)，并且通过一个引理保证在双正则二部图中能找到一个匹配，引理的证明可以在 [19] 被找到。另一方面，通过对双正则可二部图两个顶点集X与Y中点的数量跟双正则二部图中点的度建立联系，将所有的双正则可二部图分为三类。通过考虑与分析这三种类型的双正则可二部图，最终找到双正则可二部图的反魔幻标号并得出以下定理(具体证明过程将在第三部分给出)。

定理3. 每一个双正则可二部图都是反魔幻的。

2. 符号及引理

给出一个图G和 $E\left(G\right)$ 上的标号，对于 $V\left(G\right)$ 中的一个顶点v， $d_G\left(v\right)$ 表示v在G中的度，v的标号和是与顶点v所有相关联的边的标号之和，用 $\phi \left(v\right)$ 表示。对于G的一个子图H，我们用 ${\phi }_H\left(v\right)$ 表示v在H中的关联边的标号之和。对于任何两个整数a和b， $\left[a,b\right]=\left\{i\in \mathbb{Z}|a\le i\le b\right\}$ 。

我们将需要以下引理来证明定理3。

引理4. 设 $K_m$ 是一个完全图， $V\left(K_m\right)=\left\{x_1,x_2,\cdots ,x_m\right\}$ ，当使用 $\left[1+h,\frac{m\left(m-1\right)}{2}+h\right]$ 进行标号时，存在一种标号使得以下结论成立，其中h和m都是正整数，并且 $h\ge 0$ ， $m\ge 3$ 。

1) $\phi \left(x_1\right)<\phi \left(x_2\right)\cdots <\phi \left(x_m\right)$ .

2) $\phi \left(x_k\right)=\left(k-\frac{1}{2}\right)m^2-\left(k^2+k-h-\frac{3}{2}\right)m+\frac{k^3+3k^2-4k}{3}-h$ .

证明：设 $e_{i,j}=x_i{x}_j$ ，其中 $i<j\le m$ 。

当 $h=0$ 时，我们定义一个标号 $\phi :E\left(K_m\right)\to \left[1,\frac{m\left(m-1\right)}{2}\right]$ 如下：

$\phi \left(e_{i,j}\right)=\left(i-1\right)m+j-\frac{i\left(i+1\right)}{2}$ ， $\forall e_{i,j}\in E(\; K\; m\; )$

因此我们有，

$\begin{array}{c}\phi \left(x_k\right)=\phi \left(e_{1,k}\right)+\phi \left(e_{2,k}\right)+\cdots +\phi \left(e_{k-1,k}\right)+\phi \left(e_{k,k+1}\right)+\cdots +\phi \left(e_{k,m}\right)\\ =k\left(k-1\right)+{\displaystyle \underset{i=1}{\overset{k-1}{\sum }}\left[\left(i-1\right)m-\frac{i\left(i+1\right)}{2}\right]}+\left(m-k\right)\left[\left(k-1\right)m-\frac{k\left(k+1\right)}{2}\right]+\frac{m\left(m+1\right)-k\left(k+1\right)}{2}\\ =k\left(k-1\right)+\frac{\left(k-1\right)\left(k-2\right)m}{2}-\frac{\left(k-1\right)k\left(k+1\right)}{6}+\left[\left(k-1\right)m^2-\frac{k\left(k+1\right)}{2}m-k\left(k-1\right)m+\frac{\left(k^2\right)\left(k+1\right)}{2}\right]\\ +\frac{m\left(m+1\right)}{2}-\frac{k\left(k+1\right)}{2}\end{array}$

$\begin{array}{c}=\left(k-1+\frac{1}{2}\right)m^2+\left[\frac{\left(k-1\right)\left(k-2\right)}{2}-\left(\frac{3}{2}k-\frac{1}{2}\right)k+\frac{1}{2}\right]m+\left[k\left(k-1\right)-\frac{k^3-k}{6}+\frac{k^2\left(k+1\right)}{2}-\frac{k\left(k+1\right)}{2}\right]\\ =\left(k-\frac{1}{2}\right)m^2-\left(k^2+k-\frac{3}{2}\right)m+\frac{k^3+3k^2-4k}{3}\end{array}$

下一步我们证明 $\phi \left(x_k\right)$ 的单调性：

$\begin{array}{l}\phi \left(x_{k+1}\right)-\phi \left(x_k\right)\\ =\left(k+1-\frac{1}{2}\right)m^2-\left({\left(k+1\right)}^2+k+1-\frac{3}{2}\right)m+\frac{{\left(k+1\right)}^3+3{\left(k+1\right)}^2-4\left(k+1\right)}{3}\\ -\left(k-\frac{1}{2}\right)m^2-\left(k^2+k-\frac{3}{2}\right)m+\frac{k^3+3k^2-4k}{3}\\ =m^2-2\left(k+1\right)m+k^2+3k\\ =k^2+\left(3-2m\right)k+m^2-2m\end{array}$

由于 $m\ge k\ge 1$ 并且 $m\ge 3$ ，因此 $\phi \left(x_{k+1}\right)-\phi \left(x_k\right)>0$ 是显然的。

换句话说，当 $h=0$ 时， $\phi \left(x_1\right)<\phi \left(x_2\right)\cdots <\phi \left(x_m\right)$ 成立。

当 $h>0$ ，我们基于 $\phi$ 定义一个标号，如下：

${\phi }^{\prime }:E\left(K_m\right)\to \left[1+h,\frac{m\left(m-1\right)}{2}+h\right]$ , $\forall e_{i,j}\in E(\; K\; m\; )$

易得 ${\phi }^{\prime }\left(e_{i,j}\right)=\phi \left(e_{i,j}\right)+h$ 。

因此以下结论仍成立：

${\phi }^{\prime }\left(x_1\right)<{\phi }^{\prime }\left(x_2\right)\cdots <{\phi }^{\prime }(\; x\; m\; )$

并且，

$\begin{array}{c}{\phi }^{\prime }\left(x_k\right)=\phi \left(x_k\right)+\left(m-1\right)h\\ =\left(k-\frac{1}{2}\right)m^2-\left(k^2+k-\frac{3}{2}\right)m+\frac{k^3+3k^2-4k}{3}+\left(m-1\right)h\\ =\left(k-\frac{1}{2}\right)m^2-\left(k^2+k-h-\frac{3}{2}\right)m+\frac{k^3+3k^2-4k}{3}-h\end{array}$

综上所述，引理4得证。

我们需要下面这个引理来保证在二部图中能找到一个匹配，引理的证明可以在 [19] 中被找到。

引理5 ( [19] )。设H是一个二部图，顶点集是X和Y。如果在X中不存在孤立点，并且对于每一条边xy都有 $d_H\left(x\right)\ge d_H\left(y\right)$ ，其中 $x\in X$ ， $y\in Y$ ，那么H中可以找到一个饱和X中所有点的匹配。

3. 定理3证明

证明：设G是一个双正则可二部图，顶点集 $V\left(G\right)$ 划分为 $X\cup Y$ ， $X=\left\{x_1,x_2,\cdots ,x_p\right\}$ ， $Y=\left\{y_1,y_2,\cdots ,y_q\right\}$ $\left(p,q>0\right)$， $E\left[X,Y\right]$ 的导出子图是一个双正则二部图，记作B。假设 $d_B\left(x_i\right)=s$ ， $d_B\left(y_j\right)=m$ ，其中 $x_i\in X$ ， $y_j\in Y$ 。X和Y各自的导出子图都是团，我们分别记作 $K_x$ ， $K_y$ 。因此， $\left|E\left(B\right)\right|=ps=qm$ ，

$\left|E\left(G\right)\right|=ps+\frac{p\left(p-1\right)}{2}+\frac{q\left(q-1\right)}{2}$ 。

1) $p=q$

当 $p=q$ 时，G是一个正则图，在 [8] [9] [10] [11] [12] 中，所有的正则图已经被证明是反魔幻的，因此我们只需要考虑 $p\ne q$ 的情况。

2) $p\ne q$

当 $p\ne q$ 时，不妨假设 $p>q$ 。

情况(1)： $p-q\ge m-1$

现在我们按照如下步骤来构造图G的反魔幻标号。

步骤1：将 $\left[1,qm\right]$ 分配给B的所有边。

由于 $p>q$ 并且 $ps=qm$ ，可得 $d_B\left(y_j\right)=m>d_B\left(x_i\right)=s$ 。通过引理5，我们可以知道B中存在一个匹配M使Y中所有的点均饱和。不妨设这个匹配为：

$M=\left\{e_1,e_2,\cdots ,e_q\right\}$

注意到M中的所有边同时关联了X中的q个点，对于X中未饱和的 $p-q$ 点，从 $E\left[X,Y\right]$ 中各取一条它们的关联边构成边集 $M^{*}$ ，记作：

$M^{*}=\left\{e_{q+1},e_{q+2},\cdots ,e_p\right\}$

换句话说，X中的每个顶点都与 $M\cup M^{*}$ 的一条且仅有一条边相关联。

我们用 $\left[q\left(m-1\right)+1,qm\right]$ 任意来标M中的边，用 $\left[p\left(m-1\right)+1,q\left(m-1\right)\right]$ 任意来标 $M^{*}$ 中的边，然后根据这p条边的标号大小顺序，对X中的所有顶点 $x_i$ 进行重新编号，使得 $x_i$ 在 $M\cup M^{*}$ 中的关联边标号越大，i就越大。

对于 $x_k$ (其中 $k\in \left[1,p\right]$ )在B中关联的剩余未被标号的 $s-1$ 条边，用以下标号来标。

$k,k+p,k+2p,\cdots ,k+\left(s-2\right)p$

通过标号方式的步骤1 (一个例子可见图1)，我们可以得到

${\phi }_B\left(x_1\right)<{\phi }_B\left(x_2\right)\cdots <{\phi }_B\left(x_p\right)$ (1)

并且

${\phi }_B\left(x_1\right)=1+1+p+1+2p+\cdots +1+\left(s-1\right)p={\displaystyle \underset{i=0}{\overset{s-1}{\sum }}\left(1+ip\right)}$ (2)

对于点 $v\in Y$ ，接下来我们考虑 ${\phi }_B\left(v\right)$ ，不妨假设，

${\phi }_B\left(y_1\right)\le {\phi }_B\left(y_2\right)\cdots \le {\phi }_B\left(y_q\right)$ (3)

其中 $\left\{y_1,y_2,\cdots ,y_q\right\}$ 是依据 $y_j$ ( $j\in \left[1,q\right]$ )的关联边的标号和大小顺序重新编号的顶点集。另一方面，通过步骤1我们可以得到：

$\begin{array}{c}{\phi }_B\left(y_q\right)\le mq+\left(m-1\right)q+\left(m-1\right)q-1+\left(m-1\right)q-2+\cdots +\left(m-1\right)q-\left(m-2\right)\\ =mq+{\displaystyle \underset{i=0}{\overset{m-2}{\sum }}\left[\left(m-1\right)q-i\right]}\end{array}$ (4)

Figure 1. When $p-q\ge m-1$ , an example of a biregular cobipartite graph

图1. $p-q\ge m-1$ 时，一个双正则可二部图的例子

步骤2： 将 $\left[qm+1,qm+\frac{q\left(q-1\right)}{2}\right]$ 分配给 $K_y$ 的所有边。

在团 $K_y$ 上应用引理4，我们得到了

${\phi }_K\left(y_1\right)<{\phi }_K\left(y_2\right)\cdots <{\phi }_K\left(y_q\right)$ (5)

和

${\phi }_K\left(y_q\right)=\frac{q^3}{3}+\frac{\left(m-\frac{1}{2}\right)q^2}{3}$ (6)

步骤3：将 $\left[qm+\frac{q\left(q-1\right)}{2}+1,qm+\frac{q\left(q-1\right)}{2}+\frac{p\left(p-1\right)}{2}\right]$ 分配给 $K_x$ 的所有边。

在团 $K_x$ 上应用引理4，可得：

${\phi }_K\left(x_1\right)<{\phi }_K\left(x_2\right)\cdots <{\phi }_K\left(x_p\right)$ (7)

并且

${\phi }_K\left(x_1\right)=\left(p-1\right)\left(ps-\frac{q^2-q+p}{2}\right)$ (8)

由于 $\phi ={\phi }_K+{\phi }_B$ ，因此通过(1)，(3)，(5)和(7)可得

$\phi \left(y_1\right)<\phi \left(y_2\right)\cdots <\phi (\; y\; q\; )$

并且

$\phi \left(x_1\right)<\phi \left(x_2\right)\cdots <\phi (\; x\; p\; )$

如果 $\phi \left(x_1\right)>\phi \left(y_q\right)$ 成立，那么 $p-q\ge m-1$ 的情况就被证明完毕。接下来我们证明 $\phi \left(x_1\right)>\phi \left(y_q\right)$ 。根据(2)，(4)，(6)和(8)，我们可以得到：

$\begin{array}{c}\phi \left(x_1\right)-\phi \left(y_q\right)={\phi }_B\left(x_1\right)+{\phi }_K\left(x_1\right)-{\phi }_B\left(y_q\right)-{\phi }_K\left(y_q\right)\\ \ge {\displaystyle \underset{i=0}{\overset{s-1}{\sum }}\left[\left(1+ip\right)\right]}+\left(p-1\right)\left(ps-\frac{q^2-q+p}{2}\right)-\left[\frac{q^3}{3}+\left(m-\frac{1}{2}\right)q^2+\left(\frac{1}{6}-m\right)q+mq\right]+{\displaystyle \underset{i=0}{\overset{m-2}{\sum }}\left[\left(m-1\right)q-i\right]}\\ \ge \left(p-q-1\right)ps+\frac{q^3}{6}-\frac{q}{6}+\frac{pq}{2}+s+\frac{s\left(s-1\right)p}{2}-{\left(m-1\right)}^{2}q+\frac{\left(m-2\right)\left(m-1\right)}{2}\\ \ge \left(p-q-1\right)ps+\frac{p{s}^2}{2}+s+\frac{q^3}{6}-\frac{q}{6}-\left(m^2-2m+1\right)q+\frac{\left(m-2\right)\left(m-1\right)}{2}\\ >\left(p-q+\frac{s}{2}-m+1\right)ps+\frac{q^3}{6}-\frac{7q}{6}+\frac{\left(m-2\right)\left(m-1\right)}{2}\end{array}$

已知 $p-q\ge m-1$ ，因此 $p-q+\frac{s}{2}-m+1\ge 0$ 是显然。当 $q\ge 3$ 时，我们可得：

$\phi \left(x_1\right)-\phi \left(y_q\right)>0$

而当 $q=1$ 时，依据前面提到的标号方式，我们可以轻易得到：

1) $\phi \left(y_q\right)=\phi \left(y_1\right)=1+2+3+\cdots +p=\frac{p\left(p+1\right)}{2}$ .

2) $\phi \left(x_1\right)=1+1+p+2+p+\cdots +\left(p-1\right)+p=\frac{p\left(p+1\right)}{2}+\left(p-2\right)p+1$ .

显然， $\phi \left(x_1\right)>\phi \left(y_q\right)$ 。

当 $q=2$ 时，可得 $m\le p-1$ 。若 $m<p-1$ ，依据前面提到的标号方式易得。

$\phi \left(x_1\right)>\phi \left(y_q\right)$ 。若 $m=p-1$ ，可得

1) $\phi \left(y_q\right)=2p-2+2p-4+2p-5+\cdots +2p-\left(p-1-2\right)+2p-1=\frac{3}{2}{p}^2-\frac{3}{2}p+2$ .

2) $\phi \left(x_1\right)=1+1+2+3+\cdots +p-1+\left(p-1\right)\left(2p-1\right)=\frac{5}{2}{p}^2-\frac{7}{2}p+2$ .

由于 $p>q=2$ ，因此 $\phi \left(x_1\right)>\phi \left(y_q\right)$ 显然。

情况(1)证明完毕。

情况(2)： $p-q\le m-1$

接下来我们通过以下几个步骤来构造 $p-q\le m-1$ 时G的反魔幻标号。

步骤1： 将 $\left[\frac{q\left(q-1\right)}{2}+1,\frac{q\left(q-1\right)}{2}+mq\right]$ 分配给B的所有边。

由于 $p>q$ 并且 $ps=qm$ ，可得 $d_B\left(y_j\right)=m>d_B\left(x_i\right)=s$ 。通过引理(5)，我们可以知道B中存在一个匹配M使Y中所有的点均饱和。类比前文，不妨设这个匹配：

$M=\left\{e_1,e_2,\cdots ,e_q\right\}$

M中的所有边同时关联了X中的q个点，对于X中这未饱和的 $p-q$ 点，同样从 $E\left[X,Y\right]$ 中各取一条它们的关联边构成边集 $M^{*}$ ，记作：

$M^{*}=\left\{e_{q+1},e_{q+2},\cdots ,e_p\right\}$

换句话说，X中的每个顶点都与 $M\cup M^{*}$ 的一条且仅有一条边相关联。

接下来，我们用 $\left[\frac{q\left(q-1\right)}{2}+q\left(m-1\right)+1,\frac{q\left(q-1\right)}{2}+qm\right]$ 任意地来标M中的各边，用 $\left[\frac{q\left(q-1\right)}{2}+p\left(s-1\right)+1,\frac{q\left(q-1\right)}{2}+q\left(m-1\right)\right]$ 任意来标 $M^{*}$ 中的边，然后根据这p条边的标号大小顺序，对X中与p边关联的所有顶点 $x_i$ 进行重新编号，使得 $x_i$ 在 $M\cup M^{*}$ 中的关联边标号越大，i就越大。

对于 $x_k$ (其中 $k\in \left[1,p\right]$ )在B中关联的剩余未被标号的 $s-1$ 条边，用以下标号来标：

$k+\frac{q\left(q-1\right)}{2},k+1p+\frac{q\left(q-1\right)}{2},k+2p+\frac{q\left(q-1\right)}{2},\cdots ,k+\left(s-2\right)p+\frac{q\left(q-1\right)}{2}$ .

通过步骤1，我们可以得到：

${\phi }_B\left(x_1\right)<{\phi }_B\left(x_2\right)\cdots <{\phi }_B\left(x_p\right)$ (9)

并且

${\phi }_B\left(x_1\right)=1+1+p+1+2p+\cdots +1+\left(s-1\right)p+\frac{sq\left(q-1\right)}{2}={\displaystyle \underset{i=0}{\overset{s-1}{\sum }}\left(1+ip\right)+\frac{sq\left(q-1\right)}{2}}$ (10)

对于点 $v\in Y$ ，接下来我们考虑 ${\phi }_B\left(v\right)$ ，不妨假设

${\phi }_B\left(y_1\right)\le {\phi }_B\left(y_2\right)\cdots \le {\phi }_B\left(y_q\right)$ (11)

其中 $\left\{y_1,y_2,\cdots ,y_q\right\}$ 是依据 $y_j$ ( $j\in \left[1,q\right]$ )的关联边的标号和大小顺序重新编号的顶点集。另一方面，通过步骤1我们可以得到：

$\begin{array}{c}{\phi }_B\left(y_q\right)\le \left(m-1\right)q+\left(m-1\right)q-1+\cdots +\left(m-1\right)q-\left(m-2\right)+mq+\frac{mq\left(q-1\right)}{2}\\ =mq+\frac{mq\left(q-1\right)}{2}+{\displaystyle \underset{i=0}{\overset{m-2}{\sum }}\left[\left(m-1\right)q-i\right]}\end{array}$ (12)

步骤2：将 $\left[1,\frac{q\left(q-1\right)}{2}\right]$ 分配给 $K_y$ 的所有边。

在团 $K_y$ 上应用引理4，我们得到了

${\phi }_K\left(y_1\right)<{\phi }_K\left(y_2\right)\cdots <{\phi }_K\left(y_q\right)$ (13)

并且

${\phi }_K\left(y_q\right)=\frac{q^3}{3}-\frac{q^2}{2}+\frac{q}{6}$ (14)

步骤3：将 $\left[mq+\frac{q\left(q-1\right)}{2}+1,mq+\frac{q\left(q-1\right)}{2}+\frac{p\left(p-1\right)}{2}\right]$ 分配给 $K_x$ 的所有边。

在团 $K_x$ 上应用引理4，我们得到了

${\phi }_K\left(x_1\right)<{\phi }_K\left(x_2\right)\cdots <{\phi }_K\left(x_p\right)$ (15)

并且

${\phi }_K\left(x_1\right)=\frac{p\left(p-1\right)}{2}+\left(p-1\right)\left(mq+\frac{q^2-q}{2}\right)$ (16)

由于 $\phi ={\phi }_K+{\phi }_B$ ，再根据(9)，(11)，(13)和(15)可得：

$\phi \left(y_1\right)<\phi \left(y_2\right)\cdots <\phi (\; y\; q\; )$

并且

$\phi \left(x_1\right)<\phi \left(x_2\right)\cdots <\phi (\; x\; p\; )$

若 $\phi \left(x_1\right)>\phi \left(y_q\right)$ 成立，那么情形(2)则被证明。下面证明 $\phi \left(x_1\right)>\phi \left(y_q\right)$ 。首先，根据(12)和(16)，可得：

$\begin{array}{l}{\phi }_K\left(x_1\right)-{\phi }_B\left(y_q\right)\\ \ge \left(p-1\right)\left(mq+\frac{q^2-q}{2}\right)+\frac{p\left(p-1\right)}{2}-mq-{\displaystyle \underset{i=0}{\overset{m-2}{\sum }}\left[\left(m-1\right)q-i\right]}-\frac{mq\left(q-1\right)}{2}\\ =\left(p-1\right)\left(mq+\frac{q^2-q}{2}\right)+\frac{p\left(p-1\right)}{2}-m^{2}q+mq-q+\frac{\left(m-1\right)\left(m-2\right)}{2}-\frac{mq\left(q-1\right)}{2}\\ =\left(p-m\right)mq+\frac{\left(p-1\right)q\left(q-1\right)}{2}+\frac{p\left(p-1\right)}{2}-q+\frac{\left(m-1\right)\left(m-2\right)}{2}-\frac{mq\left(q-1\right)}{2}\\ \ge \frac{\left(p-1\right)q\left(q-1\right)}{2}-\frac{mq\left(q-1\right)}{2}\end{array}$

另一方面，根据(10)和(14)可得：

$\begin{array}{c}{\phi }_B\left(x_1\right)-{\phi }_K\left(y_q\right)={\displaystyle \underset{i=0}{\overset{s-1}{\sum }}\left(1+ip\right)}+\frac{sq\left(q-1\right)}{2}-\frac{q^3}{3}+\frac{q^2}{2}-\frac{q}{6}\\ =\frac{1}{2p}{\left(ps\right)}^2-\frac{1}{2}\left(ps\right)+\frac{q\left(q-1\right)}{2p}\left(ps\right)-\frac{q^3}{3}+\frac{q^2}{2}-\frac{q}{6}+s\end{array}$

因此，

$\begin{array}{c}\phi \left(x_1\right)-\phi \left(y_q\right)={\phi }_B\left(x_1\right)-{\phi }_K\left(y_q\right)+{\phi }_K\left(x_1\right)-{\phi }_B\left(y_q\right)\\ \ge \frac{1}{2p}{\left(ps\right)}^2-\frac{1}{2}\left(ps\right)+\frac{q\left(q-1\right)}{2p}\left(ps\right)-\frac{q^3}{3}+\frac{q^2}{2}-\frac{q}{6}+s+\frac{\left(p-1\right)q\left(q-1\right)}{2}-\frac{mq\left(q-1\right)}{2}\\ =\left(\frac{1}{p}+\frac{s}{2}+\frac{q\left(q-1\right)}{2p}-\frac{q}{2}\right)ps-\frac{q^3}{3}+\frac{q^2}{2}-\frac{q}{6}+\frac{\left(p-1\right)q\left(q-1\right)}{2}\\ \ge \left(\frac{1}{p}+\frac{s}{2}+\frac{q\left(q-1\right)}{2p}-\frac{q}{2}\right)ps-\frac{q^3}{3}+\frac{q^2}{2}-\frac{q}{6}+\frac{q^2\left(q-1\right)}{2}\\ =\frac{2+ps+q^2-q-pq}{2}\cdot s+\frac{q^3}{6}-\frac{q}{6}>\frac{ps+q^2-q-pq}{2}\cdot s\end{array}$

因为已知 $p-q\le m-1$ 并且 $mq=ps$ ，所以 $ps+q^2-q-pq\ge 0$ 是显然的，故 $\phi \left(x_1\right)>\phi \left(y_q\right)$ 。

综上所述，定理3得证。

基金项目

江苏省研究生科研与实践创新计划项目(NO. KYCX22_2779)。