Who would have guessed: glancing at a problem and putting down one's first hunch unchecked tends to give wrong answers :-D
Your suggestion indeed looks highly elegant: write down the adjacency matrix, take it to the n'th power, and then, as Christopher Upshaw said, simply read off... something... from the main diagonal. I guess we'd be looking for the sum of the numbers on the resulting main diagonal: the trace of the matrix.
I'll have to take a closer look, especially to find out why that works! That is, once I get my hands free, which might well happen before the Americas wake up again.