combinatorics – Upper bound for number of paths in a specific constructed graph


Assume we have the following directed graph, built from a source node $s$ a goal node $g$, which are at distance $dist(s,g)=C$ from each other, and between them there are $C$ layers with the following properties:

  • The layer at distance $t$ from $s$ is of size $2t(t+1)$ for any $t leq frac{C}{2}$
  • All the layers from $frac{C}{2}+1$ to $C$ are a mirror image of the first half of the graph (in the sense of the number of nodes in each layer)
  • All edges are only between adjucent layers (from $t$ to $t+1$)
  • there are at most 5 outgoing edges from each node and at most 5 incoming edges to each node
  • The underline graph is connected (any intermidiate node has at least 1 outgoing and 1 incoming edge)

The task is to give an upper-bound for the number of total paths from $s$ to $g$, which is tighter than $O(5^C)$ (if such thing is possible).
The point is that according to the size of each layer, there are not enough incoming edges to each layer in order for any node to have 5 edges, so I believe that the obvious bound can be improved.

The graph looks something like this (with directed edges):

enter image description here