Whoa, this is something new for me. For e.g. how would you transform calculating nth fibonacci number into a graph problem?
This is still pretty specific to counting paths in the same way the original knight problem is, though.
The other comment is talking about how you represent each state for the recursive function as a vertex, then connect it to its dependencies (basically taking the recursion tree, but merging identical calls).
Consider the following graph. The nth fibonnaci number is the number of possible walks from n to 1.
(I made a mistake in the picture, there should be an edge from 2 to 1).