Prove that if P and Q are two longest paths in a connected g

Prove that if P and Q are two longest paths in a connected graph, then P and Q have at least one vertex in common. Prove or disprove: Let G be connected graph of diameter k. If P and Q are two geodesics of length k in G, then P and Q have at least one vertex in common.

Solution

(a) Proof by contradiction that P₁ = v₀,…,v_k and P₂ = u₀ ,…, u_k are two paths of graph G of length k with no shared vertices.

As G is connected, there is a path P connecting v_i to u_j for some i,j [1,k] such that P shares no vertices with P₁ P₂ other than v_i and u_j . Say P = v_i , x₀ ,…,x_b,u_j .

Without loss of generality we may assume that i,j k/2 . Then we can construct a new path P* = v₀,…,v_i,x₁,…,x_b,u_j,…,u₁ ( by going along P₁ to v_i , then across the bridge formed by P to u_j , then along P₂ to u₀).

Obviously P* has length at least k+1 , but this contradicts the assumption that G has no paths of length greater than k. So then any two paths of length kk must intersect at at least one vertex .

(b) Let complete graph K₄ be formed by the vertices { a , b , c , d } has diameter 4 . Both ab and cd are geodesics of length 1 and do not have a common vertex . Hence , the given condition is false