证明：连通图的两条最长路必有公共点求啊求

Question

证明：连通图的两条最长路必有公共点
求啊求

Answer 1

反证法：
1）假设没有公共点（平行）,则一定是最长路长度为n,且次长路长度为m(m=n或n-1).因为最长路内部存在2条n-1的路,所以,平行的路要成为次长路,则长度不能小于n-1.
2）平行的最长路和次长路,因为属于同一连通图,所以必然有一个长度为k(k>=1)的桥梁路,将2者连通.该桥梁路不属于最长路也不属于磁场路.
3）桥梁路和最长路的连接点,将最长路分为2段,分别长度为a,n-a（a>=[n/2],设[]为向上取整）.同样的,桥梁路和次长路的连接点,将次长路分为2段,分别长度为b,m-b（b>=[m/2]）.则一定存在一条新路,长度为a+b+k.
4）m=n or n-1 -> [m/2]>=[(n-1)/2] -> b>=[(n-1)/2] -> a+b>=[n/2]+[(n-1)/2] -> a+b>=n -> a+b+k>=n+1.从而得到矛盾的结论,存在一条新路长度至少为n+1.