# co.combinatorics – 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$$).