证明每两个最长的路径至少具有一个共同的顶点

Question

如果将图$ g $连接起来，并且没有大于$ k $的路径，则证明$ k $ $ k $的每两个路径至少具有一个共同点。

我认为该通用顶点应该位于这两条路径的中间。因为如果不是这种情况，那么我们可以有一条长度$> k $的路径。我对吗？

Answer 1

假设矛盾 $ p_ {1} = langle v_ {0}， ldots，v_ {k} rangle $ $ 和 $ p_ {2} = langle u_ {0}， ldots，u_ {k} rangle $ 是两条路径 $ g $ 长度 $ k $ 没有共享顶点。

作为 $ g $ 已连接，有一条路径 $ P'$ 连接 $ v_ {i} $ 至 $ u_ {j} $ 对于一些 $ i，j in [1，k] $ 这样 $ P'$ 与 $ p_ {1} cup p_ {2} $ 以外 $ v_ {i} $ 和 $ u_ {j} $. 。说 $ p'= langle v_ {i}，x_ {0}， ldots，x_ {b}，u_ {j} rangle $ （请注意，可能没有 $ x_ {i} $ 顶点，即 $ b $ 或许 $0$ - 符号有点不足）。

没有失去普遍性，我们可能会假设 $ i，j geq lceil frac {k} {2} rceil $ （我们总是可以逆转编号）。然后我们可以构建一条新路径 $ p^{*} = langle v_ {0}， ldots，v_ {i}，x_ {1}， ldots，x_ {b}，u_ {j}， ldots， ldots，u_ {0} rangle $ $ （通过 $ p_ {1} $ 至 $ v_ {i} $, ，然后穿过由 $ P'$ 至 $ u_ {j} $, ，然后 $ P_ {2} $ 至 $ u_ {0} $).

明显地 $ p^{*} $ 至少有长度 $ K+1 $, ，但这与以下假设相矛盾。 $ g $ 没有长度大的路径大于 $ k $.

因此，任何两条长度的路径 $ k $ 必须与至少一个顶点相交，并观察到它必须在中间（如果只有一个），则如您所建议的那样。

Answer 2

正确的是，公共顶点必须出现在这两个路径的中间。

但是，直觉不会解决您要解决的实际问题。

取而代之的是，鉴于路径中的任何点，从（和包括）指向原始路径末端之一的路径段必须严格大于整个路径的一半。

一旦证明了这一点，您将能够解决被问到的问题并验证您的猜想。