# Finding a graph that minimizes the number of nodes for a given number of paths

There is a problem that is of great interest for communications and optics, but I do not know if there is an easy solution of it. We are looking for an oriented graph that goes from a node A (starting point) to a node B (ending point) that has a fixed number N different paths from A to B. Intermediate nodes that can only split or recombine two edges (so two input and two output nodes). What are the graphs that minimize the number of nodes met in all the N paths.

If I understand the problem properly, the answer should be $2 \log_2(n)$: make a graph with $\log_2(n) + 2$ layers, where the first layer is just $A$, the last layer is just $B$, and the intermediate layers have $2$ nodes each; we then put a directed edge from each node to the node(s) in the next layer. We then have $2^{\log_2(n)} = n$ paths from $A$ to $B$, and the union of these paths contains $2 \log_2(n)$ intermediate nodes.
• This only works when $n$ is a power of two. But you can get $O(\log n)$ for any $n$ by the same idea: make a graph with $\lfloor n/2\rfloor$ paths from its source to its destination, add two paths to a new destination to double the number of paths, and then add one more path if $n$ is odd. – David Eppstein Nov 8 '16 at 22:13
• You can do better. E.g., use nodes $\{1,2,\ldots,k\}$, and edges $\{(1,2), (2,3), \ldots, (k-1, k)\} \cup \{(1,3), (2, 4), \ldots, (k-2,k)\}$. Then the number of paths grows like the $k$th Fibonacci number. So $n\approx 1.62^k$, i.e., $k \approx 1.44 \log_2 n$, I think. Not sure if this is optimum, though. By a straightforward counting argument you can't do better than $\log_2 n$. – Neal Young Nov 9 '16 at 2:23