  The line graph LG of a directed graph G has a vertex for every edge of G and
an edge for every path of length 2 in G. In 1967, Knuth used the Matrix-Tree
Theorem to prove a formula for the number of spanning trees of LG, and he asked
for a bijective proof. In this paper, we give a bijective proof of a generating
function identity due to Levine which generalizes Knuth's formula. As a result
of this proof we find a bijection between binary de Bruijn sequences of degree
n and binary sequences of length 2^{n-1}. Finally, we determine the critical
groups of all the Kautz graphs and de Bruijn graphs, generalizing a result of
Levine.
