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).