# Largest number of simple paths between two vertices

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$$).

• 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?
– JimN
Sep 17, 2020 at 0:06
• @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. Sep 17, 2020 at 0:13
• I see what you mean now. Used in making a solution to the problem.
– JimN
Sep 17, 2020 at 1:31
• 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. Sep 20, 2020 at 0:09