Given $n$ nodes and $k$ edges where $n\geq 3$ and $k \geq n-1$, what is the maximum number of distinct paths that visit each node exactly once?

Question

Problem

You are given $n$ nodes and $k$ edges where $n\geq 3$ and $k \geq n-1$. You can arrange these nodes (each with its own distinct position) and edges conecting them in order to get the maximum number of (different) paths that visit each node exactly once (using the available edges only). What is this maximum number in terms of $n$ and $k$?

In the examples below we'll let $f(n,k)$ be the maximum number of paths as a function of $n$ and $k$. Also path $ABCD$ is regarded to be the same as path $DCBA$ in the examples below.

Example 1

Let $n=4$ and $k=3$. In this specific case I decided to arrange these nodes and egdes as shown in the picture below:

Based on my chosen arrangement, there's only one possible path that visits each of the $4$ nodes exactly once:

$ADCB$

which I believe is the maximum number of paths for the given nodes and edges. Hence $f(4,3)=1$

Example 2

Now let $n=4$ and $k=4$

For this case I will arrange these nodes and egdes as shown in the picture below:

Based on this arrangement, there's $4$ possible paths that visit each of the $4$ nodes exactly once:

$ABCD$, $BCDA$, $CDAB$, $DABC$

which I believe is the maximum number of paths for the given nodes and edges. Hence $f(4,4)=4$

Example 3

Similarly, given $n=4$ and $k=5$ we have the following:

With this setup, there are a maximum of $6$ paths that visit each node exactly once:

$ABCD$, $BCDA$, $CDAB$, $DABC$, $ABDC$, $ADBC$.

Hence $f(4,5)=6$

Example 4

Finally, let $n=4$ and $k=6$

I will arrange these nodes and egdes so as to get the complete graph as shown below:

Here there will be a maximum of $12$ paths with the same properties:

$ABCD$, $BCDA$, $CDAB$, $DABC$, $ABDC$, $ADBC$, $BACD$, $BCAD$, $ACDB$, $CABD$, $BDAC$, $ACBD$

Hence $f(4,6)=12$

One final note

Although the above examples can give some limited insight into what the general formula $f(n,k)$ might look like, I still don't have a clear picture of it. And since I'm currently not able to program this type of stuff I cannot produce thousands or even millions of values for $f$ in order to search for a general pattern. It's true that this is a mathematical problem and not a Computer Science one but a decent level of programming skills might be useful here. Also I realise that it might not be possible to construct an exact formula for the maximum number of paths in which case I would be interested in knowing what the best upper bound is (again in terms of $n$ and $k$).