Let $G$ be a connected graph. Prove that two longest paths in $G$ have atleast one node in common. Note that two longest paths do not neccessarily have the same length.
I began by defining two paths namely $P_1 = <v_1,…,v_k>$ and $P_2 =<u_1,…,u_m>$ where $m\neq k$ because of the note given. Now I state the definition of a conneted graph.
A graph G is connected if for each pair of vertices u; v, there is a u; v-walk
in G.
now my first intuition is to consider the fact that if no node was shared than connecting the two paths would give a (slightly ?) longer path which would make them not the largest paths. Given the fact that they are the two largest (say $n$ and $n-1$). They should be connected via atleast one node.
HOWEVER it seems odd for me to now state that this is a proof.
Best Answer
Let $P_1 = \langle v_0, \dots, v_m \rangle$ and $P_2 = \langle u_0, \dots, u_n \rangle$, such that $P_1$ and $P_2$ have no common vertices, be two different longest inextensible paths in a graph. Let us assume that $m \ge n$. Furthermore, let $v_k$ and $u_l$ be connected (in the original graph) be a path $\langle v_k, w_1, \dots, w_p, u_l \rangle$ such that neither of $w_i$ belong to either $P_1$ or $P_2$ (the length of such path is, obviously, $p+1$).
Without the loss of generality, we can assume that $k \ge m/2$ and $l \ge n/2$. This is just a matter of notation: we're labeling vertices in a way that $\langle v_0, \dots, v_k \rangle$ is longer than or equally long as $\langle v_k, \dots, v_m \rangle$ and that $\langle u_1, \dots, u_l \rangle$ is longer than or equally long as $\langle u_l, \dots, u_n \rangle$.
We construct a new path $$P := \langle v_0, \dots, v_k, w_1, \dots, w_p, u_l, \dots u_0 \rangle$$ which has length $$k + (p + 1) + l \ge m/2 + p + 1 + n/2 \ge n/2 + p + 1 + n/2 = n + p + 1 > n, $$ so $P$ is strictly longer than $P_2$ (and obviously different from $P_1$), which is a contradiction with the assumption that $P_2$ is the second longest inextensible path in the graph.