Count the paths in a graph For a given graph $G(V,E)$
$V = \{ (x,y) | x = \{0,1, ... , m\}, y = \{0,1, ... , n\} \}$
$E = \{ \{(x,y), (u,v)\} | (x=u \text{ and } |y-v|) = 1 \text{ or } (|x-u| = 1 \text{ and } y=v) \}$
How to count the number of paths between $(0,0)$ and $(m,n)$?
 A: I am not sure whether it is fair for me to write another answer as @TravisJ already wrote the solution to the problem in the comment, however, I am suggesting three different proofs.
Notice that your graph is essentially an $n\times m$ grid and you are asking for the number of paths from $(0,0)$, the bottom-left corner, to $(m, n)$, the upper-right corner, and you are only allowed to move either upwards or to the right. 
Claim. There are $\binom{n+m}{n}$ such paths.
Proof 1. Label a move upwards with $U$ and label a move to the right by $R$. Clearly the set of all valid paths is precisely the set of strings of length $n+m$ in which $R$ appears $m$ times and $U$ appears $n$ times. To count the number of such strings notice that it suffices to pick the $m$ of the $n+m$ indices for the $R$'s; the positions of the $U$'s are determined by the positions by the $R$'s (and vice versa); there are $\binom{n+m}{m}$ ways to do this. $~\blacksquare$
Proof 2. Write down the recurrence relation for the number of paths and then notice that it is in fact equivalent to the recurrence for the binomial coefficient. (I haven't worked this out in detail.) $~\blacksquare$
Proof 3. Do induction on $n+m$. Let $f(m, n)$ denote the number of paths from $(0,0)$ to $(m,n)$. We claim that $f(n,m)=\binom{n+m}{m}$. Clearly this holds in the base case. Now do the inductive step. Clearly, $f(m,n)=f(m-1,n)+f(m,n-1)=\binom{n+m-1}{m-1}+\binom{m+n-1}{m}=\binom{n+m}{m}$, where the last equality follows from the properties of the binomial coefficient. $~\blacksquare$
