彼得森图无3-节点环：围长girth=5证明中3-环部分的困惑

嘿，我来帮你把论文里这段有点跳步的论证掰明白——核心是要先补上论文默认你知道的彼得森图二元子集模型定义，这是那个3-环证明的关键前提：

彼得森图的10个顶点，可以一一对应到集合 ${1,2,3,4,5}$ 的所有二元子集（比如 ${1,2},{1,3},{2,4}$ 这类两个元素的组合，正好10个），而两个顶点相邻的规则是：它们对应的二元子集完全不交（没有公共元素）。

现在再回头看论文里的3-环证明：

无1-环或2-环；3-环：需存在3个两两不交的二元集合（不存在）；4-环：可通过证明任意两个不相邻节点的邻域恰有一个公共邻点来证；5-环：较易看出。

这里的逻辑链其实是这样的：

1. 彼得森图里的3-环，等价于存在3个两两相邻的顶点；
2. 对应到子集模型里，就是3个二元子集，每两个都得互不相交（因为相邻的定义就是子集不交）；
3. 但每个二元子集占2个元素，三个两两不交的子集总共需要 $2+2+2=6$ 个不同的元素，可我们的全集只有5个元素，根本凑不出这么多不重复的元素！
4. 所以这样的3个顶点不存在，彼得森图里自然没有3-环。

是不是一下子就通了？论文里的这句话省略了“子集模型”这个背景，才会让人摸不着头脑～

内容的提问来源于stack exchange，提问作者baxbear