# Graph combinatorial optimization problem

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?

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.
• Thank you Tony for your answer! Do you also think that, for any integer $k$, $G$ must always necessarily contain a $k$-clique? Oct 20 '21 at 19:37
• You're welcome! No, the graph will not always contains a $k$-clique. The complete multipartite graph $K_{k,k,k}$ satisfies the condition. Oct 20 '21 at 21:28