Show that there is a pair of vertices that are joined by three internally disjoint paths Show that for simple graph $G$ with $n\geq{}4$ vertices and number of edges $e>3(n-1)/2$ there is a pair of vertices that are joined by three internally disjoint paths
This brings to mind Menger's theorem but I can't figure out how to translate the edge inequality to something helpful.
 A: This is a perfect problem.
Hints:

*

*Suppose  to the contrary that any two distinct vertices of $G$
are connected by at most two of internally-disjoint paths in $G$.
We proceed by induction on $n$.


*We can assume that graph $G$ has no vertices of degree 1 (why?).


*If graph G is not connected, then at least one component $G_0$ satisfies the condition $e_0>3(n_0-1)/2$,
where $e_0$ is the number of edges of $G_0$, $n_0$ is the number of vertices of $G_0$ (why?).


*If graph $G$ is connected and has no cycles, then $G$ is a tree. So $e=n-1<3(n-1)/2$.


*Let $G$ be connected and $C$ be a cycle in $G$ of length $k\geq3$.
Then no two vertices of the cycle $C$ are connected
by a path in graph $G$ different from the paths in cycle $C$ (this is by our assumption).


*It follows that if we delete $k$ edges of cycle $C$ from $G$,
then the graph $G-E(C)$ decomposes into exactly $k$ connected graphs of $G_i$.
If in all these graphs $e_i\leq3(n_i-1)/2$, then
$$
e=k+e_1+...+e_k<=k+3(n_1-1)/2+...+3(n_k-1)/2=(3n-k)/2.
$$
On the other hand, $e>3(n-1)/2$. So
$3(n-1)<3n-k$ or $k<3$. The  contradiction follows.
