Connected Graph , common vertex proof Suppose you have a connected graph $G = (V,E)$ that has no path of length more than $2012$. Prove that any two paths $G$ of length $2012$ have a vertex in common.
My Attempt: 
Suppose for contradiction that two paths $P_{1}: v_{0} v_{1} v_{2}....v_{2012}$ and $P_{2}: u_{0} u_{1} u_{2}....u_{2012}$ share no verticies. Since the paths are connected, there must be a path of atleast length $1$ starting from some vertex $v_{i}$ of the first path $P_{1}$ and ending at some vertex $u_{j}$ of the second path $P_{2}$. $i$ and $j$ are some value from $0$ to $2012$.
I don't know where to go from this point.
 A: Continuing on your idea: there must be a path $P_3$ from $u_i$ to $v_j$ for some $i$ and $j$ that is internally disjoint from $P_1$ and $P_2$ ($P_1 \cap P_3 = \{u_i, v_j\}$ and $P_2 \cap P_3 = \{u_i, v_j\}$). Now let $P_1'$ be the path among $u_1 u_2 \dots u_i$ and $u_i u_{i+1} \dots u_{2012}$ of greatest length, and let $P_2'$ be the path among $v_1 v_2 \dots v_j$ and $v_j v_{j+1} \dots v_{2012}$ of greatest length. What can you say about the length of $P_1'$, $P_2'$, and $P_1' \cup P_2' \cup P_3$? 
A: Hint: consider two disjoint paths of length $2012$, from $a_1$ to $a_2$ and from $b_1$ to $b_2$. Since the graph is connected, there is a path from $a_i$ to $b_j$ for $i,j\in\{1,2\}$. Assume that all of those paths have length less than or equal to $2012$ and force a contradiction by showing that the paths from $a_1$ to $a_2$ and $b_1$ to $b_2$ must have length strictly less than $2012$.
A: The vertex $u_i$ partitions the path $P_1$ into two paths, one of which has at least half of the edges of $P_1$.  Similarly, the vertex $v_j$ partitions $P_2$ into two paths, one of which has at least half of the edges of $P_2$.  Obtain a path of length more than $2012$ by joining the longer part of $P_1$ with a $u_i-v_j$ path and the longer part of $P_2$.
