In every weighted graph with every edges positive and more than $11$ vertices, there exist between every vertices at most $ 2n^{2} $ shortest paths

Question

I'm trying to decide, whether the statement is true or not;

In every weighted graph with only positive edges and with at least 11 vertices, there exists at most $ 2n^{2} $ shortest paths between every two vertices, where n is the number of vertices.

Thanks!

Answer 1

False.

Consider the following graph on approximately $n$ vertices: $V(G) =$ $\{s\} +V_1 +V_2 + \ldots V_{\sqrt{n}} + \{t\}$, where

1. each $V_i$ has $\sqrt{n}$ vertices

2. there is an edge between every vertex in $V_i$ and every vertex in $V_{i+1}$ for $i=1,2,\ldots \sqrt{n}-1$, and between $s$ and every vertex in $V_1$, and between every vertex in $V_{\sqrt{n}}$ and $t$. [All edges have unit length]

There are at least $\sqrt{n}^{\sqrt{n}} >> 2 n^2$ shortest length paths from $s$ to $t$.

[If you require for every pair of vertices there to be an edge of finite positive length between them then for every pair of nonadjacent vertices in the graph as constructed above add an edge of length say $n$. This won't change the set of shortest paths.]