5
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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$
    – Penelope Benenati
    Commented Oct 20, 2021 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
    Commented Oct 20, 2021 at 21:28
  • $\begingroup$ Great answer! Thank you Tony! $\endgroup$
    – Penelope Benenati
    Commented Oct 21, 2021 at 12:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .