证明：连通图 G 中任意两条最长的轨道都有公共顶点

wilsony

谁能证明？

luyuanhong

题  证明：连通图 G 中任意两条最长的轨道都有公共顶点。

证  用反证法。

    设 G 中最长的轨道的两个端点是 A 和 B，其次最长的轨道的两个端点是 C 和 D 。

    假设 AB、CD 这两个最长、次长的轨道没有公共顶点。

    因为 G 是连通图，所以轨道 AB 上的每一点，与轨道 CD 上的每一点之间，都会有

一条轨道。设这些轨道中，最短的一条是 EF ，端点 E 在 AB 上，端点 F 在 CD 上。

由于 EF 是这样的轨道中最短的一条，因此在 EF 上，不会再有 AB、CD 上其他的顶点。

    因为 AB、CD 是 G 中最长、次长的两条轨道，其他的轨道长度不会超过 CD ，所以

                  CD ≥ AE + EF + FD ，CD ≥ CF + FE + EB 。
   
CD + CD ≥ (AE + EF + FD)+(CF + FE + EB) = (AE + EB)+(CF + FD)+ EF + FE = AB + CD + EF + FE 。

                          CD ≥ AB + EF + FE ＞ AB 。

    这就与 AB 是 G 中最长的轨道发生矛盾，所以假设不成立，AB、CD 这两个轨道必有公共顶点。

wilsony

谢谢陆老师赐教。解答中是否有个字母符号笔误？

luyuanhong

谢谢楼上 wilsony 指出我的笔误！现已更正。

wilsony

多谢陆老师！