Let $G$ be a simple graph with vertex set $V$, such that for any two vertices $u,v\in V$, we have at least $k$ edge-disjoint paths of length $2$ (i.e., formed by $2$ edges) connecting $u$ with $v$. Let $n=|V|$ be the total number of vertices of $G$.
Question: What is the minimum value of $k$, expressed as a function of $n$, to ensure that $G$ must be a complete graph?
Best Answer
The answer is $k=n-2$. To see this, first note that $k \geq n-2$, since the complete graph on $n$ vertices minus an edge has the desired property for $k=n-3$. For the other inequality suppose that $G$ is an $n$-vertex graph such that for all distinct $u, v \in V(G)$, there are at least $n-2$ edge-disjoint paths between $u$ and $v$. We claim that $G$ must be a complete graph. Suppose not. Then $ab \notin E(G)$ for some $a,b$. Let $c \notin \{a,b\}$. Then there are at most $n-3$ edge-disjoint paths of length $2$ between $a$ and $c$, which is a contradiction.