四边形无关图的最多边数问题

The Problem of Maximal Edge Number of Quadrilateral-Free Graph

摘要: 本文研究了极值图论中的一个特定问题：在一个含10个顶点的图中，当其无4–圈但必须包含至少一个三角形时，其边数的最大值是多少？通过分析相关极值图的性质并结合构造性证明，确定了该问题的精确值为14。此结果揭示了小规模极值图的结构“刚性”，即一个局部结构约束(必须存在c₃)的引入，如何显著地将其全局边数上限从16降低至14。

Abstract: This paper investigates a specific problem in extremal graph theory: determining the maximum number of edges in a graph on 10 vertices that is 4-cycle-free but is required to contain at least one triangle. By analyzing the properties of related extremal graphs and providing a constructive proof, we establish that the exact value of this maximum is 14. This result reveals the structural rigidity of small-scale extremal graphs, demonstrating how the imposition of a local constraint, the mandatory presence of a c₃ significantly reduces the graph’s global edge limit from 16 to 14.

1. 引言

极值图论是组合数学的一个核心分支，其旨在回答一个基本问题：给定一个图F，一个含n个顶点的图G在不包含F作为子图的条件下，最多能有多少条边？这个最大边数被记为$ex\left(n,F\right)$ 。这一领域由Mantel [1]在1907年对$F=K_3$ (三角形)的研究开创，并由Turán [2]在1941年将其系统地推广到$F=K_r$ (r-完全图)的情形。Turán定理及其相关问题构成了所谓的“非退化”Turán问题，其特征在于极值边数与$\left(\begin{array}{l}n\\ 2\end{array}\right)$ 同阶，即$ex\left(n,F\right)=\theta \left(n^2\right)$ 。

当被禁止的子图F是二部图时，问题的性质发生了根本性的变化。作为该领域基石之一的Erdős-Stone定理[3]指出，$ex\left(n,F\right)=\left(1-\frac{1}{\chi \left(F\right)-1}\right)\left(\begin{array}{l}n\\ 2\end{array}\right)+o\left(n^2\right)$ ，其中$\chi \left(F\right)$ 是F的色数。若F是二部图，则其色数为$\chi \left(F\right)=2$ ，此时Erdős-Stone定理仅能得出$ex\left(n,F\right)=\theta \left(n^2\right)$ 的结论。这类问题被称为“退化”的Turán型问题，其研究需要与非退化问题截然不同的方法论。

在所有退化问题中，禁止$C_4$ (4–圈)的问题是最经典和最受关注的例子之一。它等价于Zarankiewicz问题[4]的一个特例，即在$n\times n$ 的0-1矩阵中，在不允许出现$2\times 2$ 全1子矩阵的条件下，最多可以有多少个1。在图论的语言中，这即是寻找$ex\left(n,K_{2,2}\right)$ ，其中完全二部图$K_{2,2}$ 与$C_4$ 同构。里程碑式的Kővári-Sós-Turán (KST)定理[5]为这类问题提供了普适的渐近上界：$ex\left(n,K_{s,t}\right)=o\left(n^{2-\frac{1}{s}}\right)$ 对于$C_4=K_{2,2}$ ，该定理给出了$ex\left(n,C_4\right)=o\left(n^{\frac{3}{2}}\right)$ 。这一渐近界已被证明是紧的，其极值图的构造往往与有限射影平面和极图等有限几何结构深刻关联，揭示了组合学与代数、几何之间的内在联系。

本文旨在解决一个精确的、带约束的极值问题：确定在$n=10$ 个顶点的图上，同时满足无$C_4$ 子图且必须包含至少一个$C_3$ 子图的条件下，边数的最大值。我们将此值记为$ex\left(10,C_4,with{C}_3\right)$ 。

此问题与几个经典问题既有联系又有区别：它不同于研究$ex\left(n,\left\{C_3,C_4\right\}\right)$ 的问题。后者要求图中同时不含三角形和4–圈，其极值图必然是二部图，且周长至少为5 [6]。而本文的研究则要求图中必须存在三角形。它也不同于友谊定理[7]。该定理刻画了图中任意两个顶点都恰有一个公共邻居的结构。满足此条件的图必然是$C_4$ –无关的，且其结构为若干个三角形共享一个中心顶点(称为“风车图”)。友谊定理施加了一个非常强的全局性三角形结构约束。

本文所探讨的$ex\left(10,C_4,with{C}_3\right)$ 问题，处在一个微妙的中间地带。它比一般的$ex\left(10,C_4\right)$ 问题约束更强，但比友谊定理的约束更弱。这种独特的定位使其研究具有独立的价值，并预示其解可能不同于上述相关问题的结论。本文的目标是提供一个自我包含的证明，确定在$n=10$ 时该问题的精确极值。我们将证明，这个值为14。我们的研究方法是，首先通过分析一般$C_4$ –无关图的性质来建立一个理论上界，然后通过一个具体的图构造来证明该上界是紧的，从而确定其精确值。

2. 推导$ex\left(n,C_4,with{C}_3\right)$ 的上界

本节的核心策略是，首先回顾$C_4$ –无关图边数上界的一般性结论，然后通过分析相关问题的已知精确极值，利用逻辑排除法逐步排除不可能的边数，从而为我们的目标问题建立一个紧的上界。

2.1. $ex\left(n,C_4\right)$ 的一般上界：Reiman不等式

推导$C_4$ －无关图边数上界的一个经典方法是双重计数法。设$G=\left(V,E\right)$ 为一个图，其中$\left|V\right|=n,\left|E\right|=e$ ，顶点的度数序列为${\left\{d_v\right\}}_{v\in V}$ 。我们考虑所有形如$\left(u,\left\{v,w\right\}\right)$ 的有序对的集合$S$ ，其中$u\in V,\left\{v,w\right\}\subseteq N\left(u\right)$ ，即$u$ 是$v$ 和$w$ 的共同邻居。这等价于对所有以$u$ 为中心、长度为2的路径(或称“樱桃”结构)进行计数。

从中心顶点计数：对于每个度数为$d_v$ 的顶点$v$ ，它可以作为$\left(\begin{array}{c}{d}_v\\ 2\end{array}\right)$ 条长度为2的路径的中心。因此，集合$S$ 的大小为：$\left|S\right|={\displaystyle \sum {}_{v\in V}}\left(\begin{array}{c}{d}_v\\ 2\end{array}\right)$ 。

从端点对计数：由于图$G$ 是$C_4$ –无关的，任意两个不同的顶点$\left(v,w\right)$ 最多只有一个公共邻居。否则，若$u_1$ 和$u_2$ 都是$v,w$ 的公共邻居，则$v,u_1,w,u_2$ 将构成一个4–圈。因此，以不同顶点对$\left\{v,w\right\}$ 为端点的长度为2的路径最多只有一条。由于图中总共有$\left(\begin{array}{l}n\\ 2\end{array}\right)$ 个顶点对，所以$\left|S\right|$ 的大小受此限制：$\left|S\right|\le \left(\begin{array}{l}n\\ 2\end{array}\right)$ 基本不等式与求解：综合以上两种计数方法，我们得到基本不等式：

${\displaystyle \sum _{v\in V}\left(\begin{array}{l}{d}_v\\ 2\end{array}\right)}\le \left(\begin{array}{l}n\\ 2\end{array}\right)$ (1)

展开二项式系数，结合握手引理${\displaystyle \sum {}_{v\in V}}{d}_v=2e$ ，并应用Cauchy-Schwarz不等式${\left({\displaystyle \sum d_v}\right)}^2\le n\left({\displaystyle \sum d_v^2}\right)$ ，可推导出${\displaystyle \sum d_v^2}\ge \frac{4e^2}{n}$ 。将此代入展开后的基本不等式，得到：

$\frac{4e^2}{n}-2e\le n\left(n-1\right)$

整理后得到一个关于e的二次不等式：$4e^2-2ne-n^2\left(n-1\right)\le 0$ 。解此不等式可得边数e的上界，即著名的Reiman不等式：

$e\le \frac{n}{4}\left(1+\sqrt{4n-3}\right)$ (2)

2.2. 应用及逻辑排除法求精

证明 现在，我们将上述一般性结论应用于$n=10$ 的特定情形，并通过逻辑排除法逐步收紧上界。步骤一：初步上界。将代$n=10$ 入Reiman不等式：$e\le \frac{10}{4}\left(1+\sqrt{4\cdot 10-3}\right)=2.5\left(1+\sqrt{37}\right)\approx 17.708$ 由于边数e必须是整数，我们得到初步结论$e\le 17$ 。

步骤二：第一次排除(排除$e=17$ 和$e=16$ )。更精细的组合分析以及已有的研究结论表明，$e=17$ 是不可能的，并且$ex\left(10,C_4\right)$ 的精确值是$16\left(5;7\right)$ 。

$ex\left(10,C_4\right)=16$

最关键的一点是，实现这个边数上界的极值图是唯一的，并且通过检验其结构可以发现，这个唯一的(10, 16)–图是无三角形的[8]。

这一事实是我们论证的基石。由于本文研究的问题强制要求图中必须存在三角形，这个唯一的16边图因此不属于我们所允许的解空间。因此，任何满足我们问题约束的图，其边数必然严格小于16。这使我们能够严谨地建立第一个关键推论：

$ex\left(10,C_4,with{C}_3\right)\le 15$

步骤三：第二次排除(排除$e=15$ )。现在我们考察边数为15的可能性。这自然地引导我们关注另一个相关的极值问题：$ex\left(10,\left\{C_3,C_4\right\}\right)$ ，即同时禁止三角形和4–圈的图的最大边数。这个值是已知的，其极值图也是唯一的：

$ex\left(10,\left\{C_3,C_4\right\}\right)=15$

实现该边数上界的图是著名的Petersen图。Petersen图的一个核心性质就是它不含$C_3$ 和$C_4$ 。

这里的逻辑链条是无懈可击的：任何一个含有15条边的10顶点$C_4$ –无关图都必然是Petersen图。因为如果存在另一个不同的$\left(10,15\right)-C_4$ –无关图，向其加边就有可能产生一个边数大于15的$C_4$ –无关图，这将与$ex\left(10,C_4\right)=16$ 及其唯一性相矛盾。既然任何一个10顶点、15条边、$C_4$ –无关的图都必然是Petersen图，而Petersen图本身是无三角形的[9]，这就导出了一个强有力的结论：不存在一个含有15条边且满足我们问题中“含三角形”约束的$C_4$ –无关图。

这一矛盾迫使我们必须再次收紧上界，从而得出我们问题的最终上界：

$ex\left(10,C_4,with{C}_3\right)\le 14$ (3)

3. 极值图的构造性证明

通过上一节的逻辑演绎，我们已经证明了所求问题的上界为14。为了证明这个上界是紧的，我们必须构造一个满足所有条件的图，即一个有10个顶点、14条边、无$C_4$ 且含有$C_3$ 的图。

3.1. 一个(10, 14)极值图的构造

下面我们给出一个满足条件的图的构造。其顶点集为，其结构可以通过邻接表(见表1)清晰地定义。

Table 1. Adjacency list and degrees of the extremal graph $G_{14}$

表1. 极值图$G_{14}$ 的邻接表与度数

顶点	邻居	度数
0	1,2,3	3
1	0,2,4,5	4
2	0,1,6,7	4
3	0,8,9	3
4	1,8	2
5	1,9	2
6	2,8	2
7	2,9	2
8	3,4,6	3
9	3,5,7	3

3.2. 极值图的结构分析

为了更直观地理解该极值图，本节将对其结构进行分析。图$G_{14}$ 不仅仅是一个满足条件的邻接表，其内部连接方式具有一定的规律性和对称性。

从图1可以看出，$G_{14}$ 的结构可以被直观地描述为：核心三角形：图的中心是顶点$\left\{0,1,2\right\}$ 构成的三角形$\left(C_3\right)$ ，这满足了问题的核心约束。结构对称性：该图具有非平凡的对称性。例如，存在一个自同构映射$\phi$ ，它交换顶点1和2，同时交换$\left\{4,5\right\}$ 与$\left\{6,7\right\}$ (具体地，$\phi =\left(1\text{ 2}\right)\left(4\text{ 6}\right)\left(5\text{ 7}\right)$ )。这表明，从顶点1出发的结构与从顶点2出发的结构是同构的。同样，也存在交换顶点8和9的自同构。

顶点功能划分：图中的顶点可以大致分为几类：顶点$\left\{0,1,2\right\}$ 组成了核心的稠密结构、顶点3连接顶点0和远端顶点$\left\{8,9\right\}$ 的桥梁。度为2的顶点$\left\{4,5,6,7\right\}$ 起到了连接核心顶点$\left\{1,2\right\}$ 和桥接顶点$\left\{8,9\right\}$ 的作用，但它们之间没有连接，从而避免了$C_4$ 的形成。例如，$1-4-8-3-0-2-6-8$ 这样的路径展示了顶点是如何互相连接的，但$\left(1,4\right)$ 和$\left(2,6\right)$ 的邻居8是共享的，形成了路径$1-4-8-6-2$ ，但没有形成闭合的4–圈。

Figure 1. The structure of the extremal graph for $G_{14}$

图1. 极值图$G_{14}$ 的结构示意图

3.3. 图的性质验证

我们需严谨地验证图$G_{14}$ 满足所有必需的属性。

顶点数与边数：该图有10个顶点。其度数和为：

${\displaystyle \sum _{v\in V}{d}_v}=3+4+4+3+2+2+2+2+3+3=28$ (4)

根据握手引理，边数$e=\frac{1}{2}{\displaystyle \sum d_v=\frac{28}{2}=}14$ 。

三角形存在性：根据邻接表，顶点集$\left\{0,1,2\right\}$ 构成一个三角形，因为边$\left(0,1\right),\left(0,2\right),\left(1,2\right)$ 均存在于图中。因此，该图满足含有$C_3$ 的条件。

$C_4$ –无关性质：我们通过验证任意两个顶点最多只有一个公共邻居来证明该图不含4–圈。这需要对所有$\left(\begin{array}{c}10\\ 2\end{array}\right)=45$ 个顶点对进行系统性检查。下面列举部分关键检查：

$\begin{array}{l}N\left(1\right)\cap N\left(3\right)=\left\{0\right\}\\ N\left(4\right)\cap N\left(6\right)=\left\{8\right\}\\ N\left(5\right)\cap N\left(7\right)=\left\{9\right\}\\ N\left(8\right)\cap N\left(9\right)=\left\{3\right\}\\ N\left(1\right)\cap N\left(2\right)=\left\{0\right\}\\ N\left(4\right)\cap N\left(7\right)=\varphi \end{array}$

对所有45对顶点的邻居集合求交集的系统性检查证实，其交集大小均不超过1。因此，图$G_{14}$ 确实是$C_4$ –无关的。

3.4. 主要定理

通过上述分析，我们已经具备了证明本文核心结论的所有要素。

定理3.1在所有含10个顶点的$C_4$ －无关图中，若其必须包含至少一个三角形，则其最大边数为14。即：

$ex\left(10,C_4,with{C}_3\right)=14$ (5)

证明 在第2.2节中，我们通过一个逻辑排除过程证明了该问题的上界，即$ex\left(10,C_4,with{C}_3\right)\le 14$ 。该论证基于已知的极值结果$ex\left(10,C_4\right)=16$ 和$ex\left(10,\left\{C_3,C_4\right\}\right)=15$ ，并利用了其对应极值图(分别为唯一的$\left(10,16\right)$ –图和Petersen图)均为无三角形这一关键事实。

在第3.1节和第3.2节中，我们显式地构造了一个图$G_{14}$ ，并验证了它拥有10个顶点、14条边，不含$C_4^{}$ 子图，且包含一个$C_3$ 子图。这个构造证明了$ex\left(10,C_4,with{C}_3\right)\ge 14$ 。

结合上界和下界，我们得出$ex\left(10,C_4,with{C}_3\right)=14$ 。

4. 讨论与结论

4.1. 主要发现总结

本文通过对一个特定极值图论问题的逐步分析，确定了在10个顶点上，同时满足$C_4^{}$ –无关和包含$C_3^{}$ 条件的图的最大边数为14。这一结论的推导路径具有启发性：它并非通过直接求解一个带有多重约束的极值问题，而是通过分析和利用已知的、约束更少的相关问题的极值结果来收紧目标问题的可行域。下表(表2)总结了相关问题的极值数，直观地展示了不同约束条件下的边数变化。

我们证明了$ex\left(10,C_4\right)=16$ 和$ex\left(10,\left\{C_3,C_4\right\}\right)=15$ 的极值图都是无三角形的，这为我们的问题设定了14的严格上界。最后，通过一个显式的图构造，证明了此上界是紧的。

Table 2. Comparison of related extremal problems for $n=10$

表2. $n=10$ 时相关极值问题的比较

问题	约束条件	极值边数	是否含$C_3$
$ex\left(10,C_4\right)$	$C_4$ –无关	16	否
$ex\left(10,\left\{C_3,C_4\right\}\right)$	$C_3$ –无关，$C_4$ –无关	15	否
$ex\left(10,C_4,with{C}_3\right)$	$C_4$ –无关，必须含$C_3$	14	是

为了更好地理解$n=10$ 时的结果，并观$C_3$ 约束在不同顶点数下的影响，我们总结了$n<10$ 时已知的相关极值，如下表3所示。

Table 3. Comparison of related extremal problems for $n<10$

表3. $n<10$ 时相关极值问题的比较

n	$ex\left(n,C_4\right)$	$ex\left(n,\left\{C_3,C_4\right\}\right)$	$ex\left(n,\left\{C_4,with{C}_3\right\}\right)$	说明
3	3	2	3	$ex\left(3,C_4\right)$ 的极值图是$k_3^{}$ ，本身含$C_3^{}$ 。
4	3	3	3	$ex\left(4,C_4\right)$ 的极值图之一是$k_3^{}$ 。
5	6	5	6	$ex\left(5,C_4\right)$ 的唯一极值图(友谊图)含$C_3^{}$ 。
6	7	6	6	$ex\left(6,C_4\right)$ 的唯一极值图不含$C_3^{}$ 。
7	9	8	9	$ex\left(7,C_4\right)$ 的极值图(Fano平面关联图)含$C_3^{}$ 。
8	11	10	11	$ex\left(8,C_4\right)$ 的极值图含$C_3^{}$ 。
9	13	12	< 13	$ex\left(9,C_4\right)$ 的极值图之一是二部图，不含$C_3^{}$ 。

从表3中可以看出，$ex\left(n,\left\{C_4,with{C}_3\right\}\right)$ 的值是否严格小于$ex\left(n,C_4\right)$ ，取决于对应$n$ 值的$C_4$ –无关极值图本身是否含有三角形。在$n=6,9,10$ 这些情况下，$C_4$ –无关极值图恰好是无三角形的，因此强制引入$C_3$ 会导致边数的下降。

4.2. 三角形约束的结构性影响

本研究的结果清晰地展示了，在小规模图的极值问题中，一个看似微小的局部结构约束(要求存在一个三角形)可以对图的全局参数(最大边数)产生显著影响。对于$n=10$ ，这一约束将最大边数从16锐减至14。

这揭示了小规模极值图结构的“刚性”或“高度优化性”。$\left(10,16\right)-C_4$ –无关图的结构是在不产生$C_4$ 的前提下最大化边数而高度优化的产物[10]。对于$n=10$ 这个特定的顶点数，这种优化结构恰好与包含$C_3$ 不相容。一旦我们强行在图中引人一个$C_3$ ，为了维持全局的$C_4$ –无关性质，就必须打破原有的优化连接方式。这种结构性的重组会引发连锁反应，导致必须移除图中的其他若干条边以避免形成新的4–圈，最终使得图的整体边密度显著下降。这为理解局部性质如何影响全局参数提供了一个具体的、可量化的例证。

4.3. 未来研究方向

本研究的结果也为未来的探索开辟了若干途径。

问题泛化：$ex\left(n,\left\{C_4,with{C}_3\right\}\right)$ 对于一般的$n$ 表现如何？本文的结果显示，在$n=10$ 时，$C_3$ 约束导致边数上限降低。然而，对于足够大的$n$ ，情况可能有所不同。目前已知的最稠密的$C_4$ –无关图的构造，其边数达到了$ex\left(n,C_4\right)~{\frac{1}{2}}^{n^{\frac{3}{2}}}$ 的量级[7]，通常是基于有限几何(如有限域上的极图或仿射平面关联图)构建的[11]。这些代数构造的图不仅是$C_4$ –无关的，而且通常包含大量的三角形，并非二部图。例如，由奇数阶射影平面$PG\left(2,q\right)$ 构造的极图，其顶点数$n=q^2+q+1$ ，它不仅是$C_4$ –无关的，而且含有三角形。

这一事实有力地表明，当$n$ 足够大时，最大化边数的$C_4$ –无关图本身就已经满足了“包含$C_3$ ”这一条件。因此，我们有理由提出猜想：存在一个阈值$n_{\theta }$ ，当$n>n_{\theta }$ 时，$ex\left(n,\left\{C_4,with{C}_3\right\}\right)=ex\left(n,C_4\right)$ 。确定这个阈值$n_{\theta }$ 的精确值(或界限)，将是一个有趣且具有挑战性的问题。

稳定性问题：本文的论证过程隐含了图的稳定性思想。例如，我们发现边数接近$ex\left(10,C_4\right)$ 的图在结构上与极值图有很大差异。一个自然的问题是，本文构造的(10, 14)–图$G_{14}$ 是否是唯一的极值图？如果不是，那么所有满足条件的(10, 14)–图具有怎样的结构共性？此外，所有含10个顶点、13条边、无$C_4$ 且含$C_3$ 的图是否都是$G_{14}$ (或其它极值图)的子图？

改变约束：如果将$C_3$ 约束替换为其他非二部图(如$C_5$ )，即研究$ex\left(n,\left\{C_4,withF\right\}\right)$ ，其结果又将如何？不同局部结构的引入，可能会对全局边数产生不同程度的影响，从而揭示更深层次的结构依赖关系。

基金项目

商洛学院自然科学基金项目暨博士科研启动基金项目(21SKY108)、商洛学院自然科学基金项目暨国家自然科学基金重点培育项目(22KYPY10)和商洛学院2025年教育教学改革研究项目(25JYJX110)。

NOTES

^*第一作者。

^#通讯作者。