关于五个顶点不存在不对称的简单图

Simple Graphs about Five Vertices without Asymmetry

摘要: 本文讨论五个顶点不存在不对称的简单图，基于对最小度$\delta$ 进行讨论的基础上，从两个顶点是否相邻以及是否有公共邻居这个角度出发，利用反证法以及给出每种情况的具体画法，进而得出结论。近百年来，国内外很多学者都对这一问题进行了研究。由于涉及的画法较多且证明过程较为复杂，国内外关于此领域的研究进展缓慢。相比较而言，本文从特殊的视角出发使得问题较为轻松得到解决，更具创新性。

Abstract: This paper discusses the simple graph of five vertices without asymmetry, based on the discussion of the minimum degree, from the point of view of whether the two vertices are adjacent and whether there are common neighbors, the conclusion is drawn by using the counter-evidence method and the specific drawing method of each case. In the past hundred years, many scholars at home and abroad have studied this problem. Due to the many drawings involved and the complexity of the proof process, the progress of domestic and foreign research in this field has been slow. In contrast, this paper makes the problem easier to be solved from a special perspective, which is more innovative.

1. 引言

拓扑图论，作为图论领域中的一支独特分支，其研究根基可追溯至1746年欧拉提出的具有深远意义的欧拉公式[1]。这一分支的核心在于探索如何在二维平面上有效地呈现图的结构。图之所以得名如此，得益于其直观的图形化表达方式，这种视觉化的手段极大地促进了我们对图的诸多性质的深刻洞察。在现实世界中，很多复杂的情形都能抽象为由点的集合以及连接这些点的简单边所构成的图形模型来描述。

本篇论文关于五个顶点不存在不对称的简单图进行了研究，介绍了关于图论的相关基础知识，基于对最小度$\delta$ 进行讨论的基础上，从两个顶点是否相邻以及是否有公共邻居这个角度出发，通过反证法给出每种情况的具体画法[2]，进而得出结论。

2. 预备知识

为了便于读者阅读此文章，首先介绍图论的一些专用术语及其基础理论用于本文讨论的问题中。

2.1. 图的定义及其表示[3]

一个图G是指一个有序三元组$\left(V\left(G\right),E\left(G\right),{\psi }_G\right)$ ，其中$V\left(G\right)$ 是非空的顶点集，$E\left(G\right)$ 是不与$V\left(G\right)$ 相交的边集，而${\psi }_G$ 是关联函数，它使G的每条边对应于G的无序顶点对(不必相异)。若e是一条边，而u和v是使得${\psi }_G\left(e\right)=uv$ 的顶点，则称e连接u和v；顶点u和v称为e的端点。在图G中将顶点集的数量记为n，边集的数量记为m。

例如，$G=\left(V\left(G\right),E\left(G\right)\right)$ ，令

$V\left(G\right)=\left\{v_0,v_1,v_2,v_3,v_4,v_5\right\}$ ，$E\left(G\right)=\left\{e_1,e_2,e_3,e_4,e_5,e_6,e_7,e_8,e_9,e_{10}\right\}$ ，${\psi }_G$ 被定义为

${\psi }_G\left(e_1\right)=v_1{v}_2$ ，${\psi }_G\left(e_2\right)=v_2{v}_3$ ，${\psi }_G\left(e_3\right)=v_3{v}_4$ ，${\psi }_G\left(e_4\right)=v_4{v}_5$ ，${\psi }_G\left(e_5\right)=v_5{v}_1$

${\psi }_G\left(e_6\right)=v_0{v}_1$ ，${\psi }_G\left(e_7\right)=v_0{v}_2$ ，${\psi }_G\left(e_8\right)=v_0{v}_3$ ，${\psi }_G\left(e_9\right)=v_0{v}_4$ ，${\psi }_G\left(e_{10}\right)=v_0{v}_5$

此时，$m=10,n=5$ 。

2.2. 图的画法

在一个平面上，一个图的画法是从该图形到平面的一一映射。此映射将图的每个顶点映射到平面上的点(为了清晰可见，我们把点用小圆圈表示)，把连接这些点的简单曲线来表示边。

2.3. 同构和自同构

已知两个图G和图H,，如果存在两个一一映射$\theta$ ：$V\left(G\right)\to V\left(H\right)$ 和$\varphi$ ：$E\left(G\right)\to E\left(H\right)$ ，使得${\psi }_G\left(e\right)=uv$ 当且仅当${\psi }_H\left(\phi \left(e\right)\right)=\theta \left(u\right)\theta \left(v\right)$ ，这样一个映射对$\left(\theta ,\varphi \right)$ 称为G和H之间的一个同构，则称图G和图H是同构的，记作$G\cong H$ 。

一个图G的自同构是指图G与自身的一个同构。

一个图G的自同构反映出它的对称性。

2.4. 图论中的一些术语定义

关联：一条边的端点被称为与边关联。

相邻：与公共边关联的两个顶点是相邻的，与公共顶点关联的两条边也是相邻的。

邻居：两个不同的相邻顶点是邻居。图G中顶点v的邻居集由$N_G\left(v\right)$ 表示。

相似顶点：一个简单图G存在自同构$\alpha$ 将u映射到v，则$u$ 和v在图G中是相似的。

非对称图：没有两个顶点相似的图。

2.5. 度

在图G中，一个顶点v的度$d_G\left(v\right)$ 是指G中与v关联的边的数目，每个环算作两条边。用$\delta \left(G\right)$ 和$\Delta \left(G\right)$ 分别表示G的顶点的最小度和最大度。特别地，如果G是一个简单图，那么$d_G\left(v\right)$ 是G中顶点v的邻居的数目。度为零的顶点称为孤立点[4]。

3. 关于五个顶点不存在不对称的简单图的证明

一个简单图G，往证若$\left|V\left(G\right)\right|=5$ ，存在$u,v\in V\left(G\right)$ ，u与v相似。首先考虑讨论G的所有可能，通过反证法，只需证明任意$u,v\in V\left(G\right)$ ，u与v不相似。

设$V\left(G\right)=\left\{v_0,v_1,\cdots ,v_4\right\}$ ，不失一般性，令$d_G\left(v_0\right)\le d_G\left(v_1\right)\le d_G\left(v_2\right)\le d_G\left(v_3\right)\le d_G\left(v_4\right)$ 。接下来对最小度$\delta$ 进行讨论，$0\le \delta \le 4$ 。设$\delta =d_G\left(v_0\right)$ ，$\delta =0$ 时，则必有$d_G\left(v_1\right)\ge 1$ ，否则$d_G\left(v_1\right)=0$ ，那么其他点可以看成恒等映射，$v_0,v_1$ 这两个点进行置换，那么$v_0,v_1$ 就是相似的，矛盾。$v_0$ 是孤立点，则剩余四个点不存在不对称的简单图显然成立。

4. 讨论最小度为1的所有情形

若存在$d_G\left(u\right)=d_G\left(v\right)$ ，则$1\le d_G\left(u\right)\le 4$ ，若$d_G\left(u\right)=d_G\left(v\right)=4$ 时(如图1)，$\delta \ne 1$ 与$\delta =1$ 矛盾。$d_G\left(u\right)=d_G\left(v\right)=1$ ，u与v相邻时(如图2)以下所有图中仅画出当前可以确定的边。无论剩余的三个点之

间是否相邻都不影响u与v相似，则矛盾。u与v不相邻且无公共点为邻居时(如图3)，x与w相邻时，u与v相似，则矛盾；x与w不相邻时，u与x相似，则矛盾。u与v不相邻且有一个公共邻居w时(如图4)，无论x、y、w之间是否相邻都不影响u与v相似，则矛盾。

Figure 1. Give the vertices u and v in 4 degrees

图1. 给出顶点u与v的度均为4的画法

Figure 2. The vertices u and v are adjacent and have degrees of one

图2. 给出顶点u与v相邻且度均为1的画法

Figure 3. The vertices u and v are not adjacent, the degrees are one, and have no common neighbors

图3. 给出顶点u与v不相邻，度均为1且无公共邻居的画法

Figure 4. The vertices u and v are not adjacent, the degrees are one, and have a common neighbor

图4. 给出顶点u与v不相邻，度均为1且有一个公共邻居的画法

当$d_G\left(u\right)=d_G\left(v\right)=2$ 时，u与v相邻且无公共邻居时(如图5)，此时为$P_5$ ，w与v相似，则矛盾。u与v相邻且有一个公共邻居w时(如图6)，u与v相似，则矛盾。u与v不相邻且无公共邻居时(如图7)，此时$\left|V\left(G\right)\right|=6$ ，矛盾。u与v不相邻且有一个公共邻居w时(如图8)，不失一般性，设当w与x相邻时，u与x相似，矛盾；当w与x相邻且w与y相邻时，u与v相似，矛盾。u与v不相邻且有两个公共邻居x和w时(如图9)，无论x与w相邻且w与y相邻、w与y相邻、x与y相邻、x与y相邻且x与w相邻都不影响u与v相似，则矛盾。

Figure 5. The vertices u and v are adjacent, with degrees of two and no common neighbors

图5. 给出顶点u与v相邻，度均为2且无公共邻居的画法

Figure 6. The vertices u and v are adjacent, with degrees of two and have a common neighbor

图6. 给出顶点u与v相邻，度均为2且有一个公共邻居的画法

Figure 7. The vertices u and v are not adjacent, the degrees are both two, and there are no common neighbors

图7. 给出顶点u与v不相邻，度均为2且无公共邻居的画法

Figure 8. Give the vertices u and v are not adjacent, the degrees are both two, and have a common neighbor

图8. 给出顶点u与v不相邻，度均为2且有一个公共邻居的画法

Figure 9. The vertices u and v are not adjacent, the degrees are both two, and there are two common neighbors

图9. 给出顶点u与v不相邻，度均为2且有两个公共邻居的画法

当$d_G\left(u\right)=d_G\left(v\right)=3$ 时，u与v相邻且无公共邻居时(如图10)，此时$\left|V\left(G\right)\right|=6$ ，矛盾。u与v相邻且有一个公共邻居w时(如图11)，此时u与v相似，则矛盾。u与v相邻且有两个公共邻居x与y时(如图12)，无论x与y相邻且y与w相邻、y与w相邻、x与w相邻、x与y相邻且x与w相邻都不影响u与v相似，则矛盾。u与v不相邻且无公共邻居时(如图13)，此时$\left|V\left(G\right)\right|=8$ ，则矛盾。u与v不相邻且有一个公共邻居x时(如图14)，此时$\left|V\left(G\right)\right|=7$ ，则矛盾。u与v不相邻且有两个公共邻居w与x时(如图15)，此时$\left|V\left(G\right)\right|=6$ ，则矛盾。u与v不相邻且有三个公共邻居w、x、y时(如图16)，$\delta \ne 1$ 与$\delta =1$ 矛盾。

Figure 10. The vertices u and v are adjacent, the degrees are both three, and have no common neighbor

图10. 给出顶点u与v相邻，度均为3且无公共邻居的画法

Figure 11. The vertices u and v are adjacent, the degrees are both three, and have a common neighbor

图11. 给出顶点u与v相邻，度均为3且有一个公共邻居的画法

Figure 12. The vertices u and v are adjacent, the degrees are three, and have two common neighbors

图12. 给出顶点u与v相邻，度均为3且有两个公共邻居的画法

Figure 13. The vertices u and v are not adjacent, the degrees are both three, and there are no common neighbors

图13. 给出顶点u与v不相邻，度均为3且无公共邻居的画法

Figure 14. The vertices u and v are not adjacent, the degrees are three and have a common neighbor

图14. 给出顶点u与v不相邻，度均为3且有一个公共邻居的画法

Figure 15. The vertices u and v are not adjacent, the degrees are both three, and there are two common neighbors

图15. 给出顶点u与v不相邻，度均为3且有两个公共邻居的画法

Figure 16. The vertices u and v are not adjacent, the degrees are both three, and there are three common neighbors

图16. 给出顶点u与v不相邻，度均为3且有三个公共邻居的画法

5. 讨论最小度为2的所有情形

存在$d_G\left(u\right)=d_G\left(v\right)$ ，则$2\le d_G\left(u\right)\le 4$ ，若$d_G\left(u\right)=d_G\left(v\right)=2$ 时，u与v相邻且无公共邻居时(如图17)，无论x、y之间是否相邻都不影响u与v相似，则矛盾。u与v相邻且有一个公共邻居w时(如图18)，u与v相似，则矛盾。u与v不相邻且无公共邻居时(如图7)，矛盾。u与v不相邻且有一个公共邻居w时(如图19)，无论x、y之间是否相邻都不影响u与v相似，则矛盾。u与v不相邻且有两个公共邻居w、x时(如图20)，y与v相似，则矛盾。

Figure 17. The minimum degree is two, the vertices u and v are adjacent, the degrees are both two, and there is no common neighbor

图17. 给出最小度为2，顶点u与v相邻，度均为2且无公共邻居的画法

Figure 18. The minimum degree is two, the vertices u and v are adjacent, the degrees are both two, and have a common neighbor.

图18. 给出最小度为2，顶点u与v相邻，度均为2且有一个公共邻居的画法

Figure 19. The minimum degree is two, the vertices u and v are not adjacent, the degrees are both 2, and there is a common neighbor

图19. 给出最小度为2，顶点u与v不相邻，度均为2且有一个公共邻居的画法

Figure 20. Give a minimum degree of two, the vertices u and v are not adjacent, degrees are two, and there are two common neighbors

图20. 给出最小度为2，顶点u与v不相邻，度均为2且有两个公共邻居的画法

若$d_G\left(u\right)=d_G\left(v\right)=3$ 时，u与v不相邻时(如图16)，矛盾。u与v相邻且无公共邻居时(如图10)，$\left|V\left(G\right)\right|=8$ ，则矛盾。u与v相邻且有一个公共邻居w时(如图21)，若w、x、y之间两两相邻，则$\delta \ne 2$ 与$\delta =2$ 矛盾；若w与x相邻、x与y相邻，则v与x相似，矛盾；若w与x相邻、w与y相邻，则u与v相似，矛盾。u与v相邻且有两个公共邻居x与y时(如图22所示)，则x与y相似，矛盾。

Figure 21. Give a minimum degree of two, vertices u and v are adjacent, both degrees are three, and have a common neighbor

图21. 给出最小度为2，顶点u与v相邻，度均为3且有一个公共邻居的画法

Figure 22. Give a minimum degree of two, vertices u and v are adjacent, both degrees are three, and have two common neighbors

图22. 给出最小度为2，顶点u与v相邻，度均为3且有两个公共邻居的画法

若$d_G\left(u\right)=d_G\left(v\right)=4$ 时，u与v必须相邻(如图1所示)，u与v相似，矛盾。

6. 讨论最小度为3的所有情形

存在$d_G\left(u\right)=d_G\left(v\right)$ ，则$3\le d_G\left(u\right)\le 4$ ，若$d_G\left(u\right)=d_G\left(v\right)=3$ 时，u与v不相邻时(如图23所示)，w、x、y之间至少两条边相邻，无论哪种情形都不影响u与v相似，矛盾。u与v不相邻且无公共邻居时(如图13)，矛盾。u与v相邻且无公共邻居时(如图10)，矛盾。u与v相邻且有一个公共邻居w时(如图24)，u与v相似，矛盾。u与v相邻且有两个公共邻居时(如图22)，此时$\delta \ne 3$ 与$\delta =3$ 矛盾。

若$d_G\left(u\right)=d_G\left(v\right)=4$ 时，u与v必须相邻(如图1所示)，w、x、y之间至少两条边相邻，无论哪种情形都不影响u与v相似，矛盾。

Figure 23. The minimum degree is three, the vertices u and v are not adjacent, and the degrees are three

图23. 给出最小度为3，顶点u与v不相邻，度均为3的画法

Figure 24. Give a minimum degree of three, vertices u and v are adjacent, both degrees are three, and have a common neighbor

图24. 给出最小度为3，顶点u与v相邻，度均为3且有一个公共邻居的画法

7. 讨论最小度为4的所有情形

对于这样的图比较特殊(如图25所示)，它为顶点为5的完全图。任意两点都相似，故矛盾。

Figure 25. A complete graph with a vertex of five

图25. 顶点为5的完全图

8. 结论

本文介绍了关于图论的基础知识，基于对最小度$\delta$ 进行讨论的基础上，从两个顶点是否相邻以及是否有公共邻居这个角度出发，通过反证法给出每种情况的具体画法，进而得出五个顶点不存在不对称的简单图。