Let $G$ be a simple undirected graph, $f(v, u)$ be the number of simple paths between $u$ and $v$ in $G$, $f(G) = \max f(v, u)$ over all pairs of vertices $v, u \in G$.

A recent IOI problem utilized the fact that there is no graph with $f(G) = 3$. Are there any other values of $k \geq 1$ such that no graph with $f(G) = k$ exists?

Computationally, all positive $k \neq 3$ not exceeding $50$ have $f(G) = k$ with $G$ having at most $8$ vertices (in fact, only $k = 45$ requires more than $7$).

  • $\begingroup$ It doesn't look to me like that fact was used in the IOI problem ... from what I understood, their example 3 simply says that there is no way to have 3 simple paths between two vertices in a graph with $|V|=2$. Is your fact about your defined $f(u,v)$ verified? $\endgroup$
    – JimN
    Sep 17, 2020 at 0:06
  • 1
    $\begingroup$ @JimN Yes: if $f(v, u) = 3$, we can always find $v', u'$ such that $f(v', u') > 3$. Since all prescribed $f(v, u) \leq 3$, then if you see $f(v, u) = 3$, you can immediately determine that no such graph exists. $\endgroup$ Sep 17, 2020 at 0:13
  • $\begingroup$ I see what you mean now. Used in making a solution to the problem. $\endgroup$
    – JimN
    Sep 17, 2020 at 1:31
  • 2
    $\begingroup$ Any $k=ab;a,b\ge 2$ can be realized as $f(G)$ for a graph $G$ obtained by gluing $K_{2,a}$ and $K_{2,b}$ by a vertex, so the question can be reduced to primes. $\endgroup$ Sep 20, 2020 at 0:09


Your Answer

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

Browse other questions tagged or ask your own question.