If there are more than $\frac{3(n-1)}{2}$ edges then there exist veritces $u,v$ with $3$ vertex-disjoint $(u,v)$-paths 
If a graph $G$ with $n \geq 4$ vertices has more than $\frac{3(n-1)}{2}$ edges then there exist $u,v \in V(G)$ with $3$ vertex-disjoint $(u,v)$-paths.

I tried induction but didn't work. Can someone provide me with a hint on how to start?
 A: Note that the restriction $n\ge4$ is irrelevant because for $1\le n\le 3$, we have ${n\choose 3}\le\frac {3(n-1)}2$.
Assume $G$ contains a triangle, i.e., vertices $u,v,w$ with edges $uv,vw,wu$. Let $G'$ be $G$ with these three edges removed.
Assume there is a path in $G'$ betwen two of the vertices $u,v,w$ and wlog $uz_1\ldots z_mv$ is the shortest such path. Then none of the $z_i$ equals $w$ and so on $G$ we have $uz_1\ldots z_mv$, $uwv$ and $uv$ and are done.
Hence $G'$ splits into three disjoint graphs $G_u,G_v,G_w$ with $n_u,n_v,n_w$ vertices and $e_u,e_v,e_w$ edges.
We have
$$\begin{align}e_u+e_v+e_w&=e-3\\&>\frac{3(n-3)}2\\&=\frac{3(n_u-1)}2+\frac{3(n_v-1)}2+\frac{3(n_w-1)}2\end{align}$$
so that at least one of the $G_x$ has $e_x>\frac{3(n_x-1)}2$ and we are done.
We may therefore assume henceforth  that $G$ contains no triangle.
Let $uv$ be any edge. Then $u,v $ have no neighbours in common. Hence we obtain a simple graph $G'$ with $n'=n-1$ vertices and $e'=e-1>\frac{3(n-1)}2-1>\frac{3(n'-1)}2$ edges by merging $u$ and $v$ (into $u$). By induction hypothesis, $G'$ has the desired property. Let $xz_1\ldots z_my$, $xz_1'\ldots z_{m'}'y$, $xz_1''\ldots z''_{m''}y$ be three vertex disjoint paths in $G'$. If any of the edges involved is from $u$ to a neighbour of $v$, we can insert $v$ between these points in the path and obtain three paths in $G$. 
If we have to add $v$ this way at most once, we are done.
Hence suppose we have to add $v$ at least twice. Then $u$ occurs twice in the pats and must be an endpoint, wlog. $u=x$. If we need to insert $v$ all three times, we have $vz_1\ldots z_m y$, $vz_1'\ldots z'_{m'} y$, $vz_1''\ldots z''_{m''} y$, and are done. Hence assume we insert $v$ only twice, say in the $z'$ and the $z''$ path. Then we have $vz_1'\ldots z'_{m'} y$, $vz_1''\ldots z''_{m''} y$, $vuz_1\ldots z_m y$, and are done.
