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.

  • $\begingroup$ Thank you Tony for your answer! Do you also think that, for any integer $k$, $G$ must always necessarily contain a $k$-clique? $\endgroup$ Oct 20 '21 at 19:37
  • 1
    $\begingroup$ You're welcome! No, the graph will not always contains a $k$-clique. The complete multipartite graph $K_{k,k,k}$ satisfies the condition. $\endgroup$
    – Tony Huynh
    Oct 20 '21 at 21:28
  • $\begingroup$ Great answer! Thank you Tony! $\endgroup$ Oct 21 '21 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.