A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ corresponds to a minimal separator. In general, $G$ can have more than one clique tree representing it. A graph is said to be geodetic if the shortest path between any pair of vertices is unique.
Consider a chordal graph $G$ in which every minimal separator is a singleton set. I can prove such a graph is geodetic, but this property doesn't hold once minimal separators get larger. For example, consider a graph with a minimal separator $S = \{2,3\}$ of size 2 below. It already has 2 shortest paths between the vertices 1 and 4.
In fact, consider two adjacent vertices in a clique tree of a chordal graph. Let $S$ be the minimal separator corresponding to the edge between them. Now consider two distinct vertices $u$ and $v$ in these adjacent cliques such that $u,v \notin S$. The number of shortest paths from $u$ to $v$ is the size of the minimal separator between them. This is because, roughly speaking, it takes one step to move from any vertex in a clique to a separator, and likewise any vertex in a clique can be reached with one step from the separator.
Finally, consider an example like below. The graph has 3 maximal cliques, and the minimal separators are $\{ 4,5 \}$ and $\{ 2,3 \}$. Now the number of shortest paths from 1 to 6 is $2 \times 2 = 4$.
Given a connected chordal graph $G$ (with no loops nor parallel edges), what is the maximum number of shortest paths there can exist between any pair of vertices? How can it be bounded (in terms of $n$ and $m$)?
