# Longest Path in a Directed Graph with Specified Number of Edges

Let $G$ be a directed graph that has $n$ nodes and is strongly connected. Define a random path as the following: Pick two vertices uniformly at random and find the shortest path going from one vertex to another (either way is fine). Can we bound the length of a random path of $G$ if we know the size of $|E|$?

For example, if $E = O(n)$, then it seems easy to construct a graph with only large paths. However, if $E = \Theta(n^2)$, then it is likely that the graph has short expected path size. What if $|E| = o(n^2)$ or $O(n \log n)$ ? Can we derive any bounds for the expected length of a random path in these cases? What if our graph is undirected?

• I guess that all edges have equal length? – Manfred Weis Jan 25 '18 at 5:01
• What do you mean by random path? – Fedor Petrov Jan 25 '18 at 6:36
• @FedorPetrov I have edited to make this more clear – Largest Prime Jan 25 '18 at 13:47

Even if $E$ grows as $cn^2$, the random path may have length about $n$. Consider a complete graph on $n/2$ vertices joined with a path of length $n/2$.