Suppose that two paths P1 and P2 are both longest paths in a

Suppose that two paths P_1 and P_2 are both longest paths in a connected graph G. Show that they must have at least one vertex in common.

Solution

Connected Graph-A graph is connected when there is a path between every pair of vertices.

Proof-We will prove this by contradiction.

Assume that there is no such common vertex.Given G is connected then there exists u,v such that u belongs to P1 and v belongs to P2, such that there is a path from u to v that does not include any other vertices in P1 and P2.(keep in mind note that u and v cannnot be endpoint of P1 and P2 as P1 and P2 can be merged to get longer path.)

let u divide P1 into paths p1 and p2 with length x1 and x2.WLOG(without loss of generality),assume that x1 x2. Similarly, let v divide P2 into paths p3 and p4 with lengths y1 and y2 respectively. (WLOG) Without loss of generality, assume that y1 y2. Then, x1 M/2 and y1 M/2 where M = x1 + x2 = y1 + y2.

Consider the path P\' formed by < P1 >, u, v, < Q2>. Then |P \' | > x1 + y1. Hence |P\' | > M.(because M=x1+x2) Hence P1 and P2 could not have been the maximum length paths in G. which is a contradiction.hence,P1 and P2 must have atleast one vertex in common.