What is the relationship between shortest path and density for undirected graph? Does the shortest path increase or decrease with graph density in undirected graphs? Or is there no clear relationship?
 A: Here's an "experimental mathematics" answer.
The following plot shows the average path length vs. graph density in Erdős–Rényi random graphs $G(50,p)$: 10 samples for each probability $p \in \{0.01,0.02,\ldots,1\}$.

Generally, we can see that graphs with higher density have shorter average path length (which is intuitive).
Note: Some of the graphs with close-to-$0$ densities have a small "average path length", but this is an anomaly of the definition (if there's no path, they have path length $0$).
Comments:


*

*It is likely that under different random graph models the behaviour is different (as, perhaps, it might be for, say, real-world networks).

*There are probably going to be contrived examples far away from the main curve, but the experimental results above suggest they will be relatively rare.


[The above figure was computed in R using the igraph extension.  The relevant functions are  average.path.length and graph.density.  I also plotted the results using tikzDevice, making some manual edits.]
