Hamilton Cycles
Hamilton Cycles
复制标题
汉密尔顿自行车
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Frank de Zeeuw
中科院分区：
文献类型：
--
作者：
Frank de Zeeuw
让我们证明它没有10圈，所以周长是9。我们认为彼得森图是一个外部5-圈和一个内部5-圈，由5个链接连接。一个10圈必须包含偶数个这样的链接，而不是0，因为这样我们就不会得到一个连通子图。直到同构，这留下以下两种情况：两个链接或四个链接（用粗黑边描绘）;注意，在两个链接的情况下，它们必须击中两个5-圈之一上的相邻顶点，因此在可能交换5-圈之后，这是唯一的两个链接的情况。在每种情况下，我们用红色标记不能在循环中的边缘，用绿色标记必须在循环中的边缘。当顶点有一条红色边时，它的另外两条边必须是绿色或黑色。如果顶点的两条边是绿色或黑色，那么第三条边必须是红色。这样，我们在两种情况下都得到了矛盾，要么是因为顶点的度数是3，要么是因为5-圈。
Let us prove that it has no 10-cycle, so the circumference is 9. We think of the Petersen graph as an outside 5-cycle and an inside 5-cycle, connected by 5 links. A 10-cycle would have to contain an even number of such links, and not 0 since then we would not get a connected subgraph. Up to isomorphism, this leaves the two cases below: two links or four links (depicted with thick black edges); note that in the case of two links, they must hit adjacent vertices on one of the two 5-cycles, so after possibly swapping the 5-cycles, this is the only case with two links. In each case, we mark edges that cannot be in the cycle with red, and edges that must be in the cycle with green. Whenever a vertex has a red edge, its other two edges must be green or black. And if two edges of a vertex are green or black, then the third edge must be red. In this way we get a contradiction in both cases, either because of a vertex of degree 3 or because of a 5-cycle.