# Graph Theory - Finding Number of paths

Consider a directed graph $D(n)$ whose vertex set $V$ consists of the integers $1,2,\dots,n$, and whose edge set $E$ consists of ordered pairs of integers $(i,j)$ whenever $i < j$. In other words, there is a directed edge from $i$ to $j$ if and only if $i < j$. For example, the figure below shows $D(5).$

a. In $D(n)$, a path from $1$ to $n$ is described by a sequence of vertices $v1,v2,...,v_k$ where $v_1= 1$, $v_i< v_{i+1}$ for $i = 1,\dots,k − 1$, and $v_k= n$. For $D(5)$ above, please list all the paths from $1$ to $5$. (There should be $8$ of them.)

b. Suppose $P = v_1,v_2,\dots,v_k$ is a $1$-to-$n$ path in $D(n)$. Let $f(P) = \{v2,\dots,v_{k−1}\}$. For example, for $D(5)$, $f(1,2,4,5) = \{2,4\}$. Please explain why $f$ is one-to-one.

c. Next, explain why $f$ is onto.

d. From b and c, we conclude that $f$ is a bijection. What then does this imply about the number of $1$-to-$n$ paths in $D(n)$? (Note: your answer here should be a generalization of your answer in (a).)

Any ideas or hint or ... ?

-

The map $f$ that you need for (b)-(d) is poorly explained, since the problem does not say what its codomain is. I’ll expand on the definition a bit.

Let $P$ be the set of paths from $1$ to $n$ in $D_n$. Let $Q$ be the set of all paths, including the empty path, in the subgraph of $D_n$ induced by the vertices $\{2,\dots,n-1\}$. For any path $$\langle 1=v_1,v_2,\dots,v_{k-1},v_k=n\rangle\in P$$ let $f\big(\langle 1,v_2,\dots,v_{k-1},n\rangle\big)=\langle v_2,\dots,v_{k-1}\rangle\in Q$.

Example: In $D_5$ the sets $P$ and $Q$ contain the following paths:

$$\begin{array}{l|l} P&Q\\ \hline \langle 1,5\rangle&\varnothing\\ \langle 1,2,5\rangle&\langle 2\rangle\\ \langle 1,3,5\rangle&\langle 3\rangle\\ \langle 1,4,5\rangle&\langle 4\rangle\\ \langle 1,2,3,5\rangle&\langle 2,3\rangle\\ \langle 1,2,4,5\rangle&\langle 2,4\rangle\\ \langle 1,3,4,5\rangle&\langle 3,4\rangle\\ \langle 1,2,3,4,5\rangle&\langle 2,3,4\rangle \end{array}$$

The first column of this table actually answers (a). Parts (b) and (c) are very straightforward, especially if you realize that a path in $D_n$ is completely determined by the set of vertices: if we have the set, we can always order it correctly. Thus, $P$ corresponds in a straightforward way to the subsets of $\{1,\dots,n\}$ that contain both $1$ and $n$, and $Q$ corresponds in an equally straightforward way to the subsets of $\{1,\dots,n\}$ that contain neither of $1$ and $n$.

For (d) they want you to use to use the fact that $P$ and $Q$ have the same cardinality, since there is a bijection between them, and to notice that $|Q|$ is very easy to calculate. If you have trouble here, try counting by hand the paths from $1$ to $n$ in $D_n$ for $n=1,2,3,4,5$; if you do it right, you’ll see a pretty obvious pattern.

-

I'll leave (a) to you.

For (b) and (c), note that a path from $1$ to $n$ will always start at $1$ and end at $n$, so paths determine, and are uniquely determined by, the set of intermediate vertices on the path. Note that in (c), I'm assuming the codomain is the set of all subsets of $\{2,...,n-1\}$.

For (d), since a path is uniquely determined by the set of intermediate vertices on the path, of which there are $n-2$ (for $n\geq 2$), then there are $2^{n-2}$ possible paths from $1$ to $n$ for $n\ge2$. Of course, for $n=1$, there's only one path, but that's the only one that doesn't really fit the pattern. I suppose that you could say that there are $\left\lceil 2^{n-2}\right\rceil$ paths from $1$ to $n$ possible, if you wanted it to hold for all $n$.

-