Introduction
This blog is inspired by this blog, which is an interesting constructive problem:
- How to construct a DAG with no multiple edges, such that there exists exactly $$$k$$$ distinct paths from vertex $$$1$$$ to $$$n$$$?
Obviously, there is a trivial solution which requires $$$2k$$$ edges and $$$k+2$$$ vertices. Simply connect vertex $$$1$$$ to each vertex numbered from $$$2$$$ to $$$k+1$$$, then connect each of these vertices to vertex $$$k+2$$$. In this blog, we shall discuss how to minimise the number of edges used.
Task $$$1$$$: Using no more than $$$4 \log k$$$ edges
This is likely to be the first way that many people will approach this problem. Consider the following structure: 
There are exactly $$$2$$$ distinct paths from $$$1$$$ to $$$3$$$. If we chain them together as such: 
