Line-digraphs, arborescences, and theorems of tutte and knuth

AbstractThe line-digraph of a digraph D with vertices V1, …, Vn is the digraph D∗ obtained from D by associating with each edge of D a vertex of D∗, and then directing an edge from vertex (Vi, Vj) of D∗ to vertex (Vk, Vm) if and only if j = k. This paper extends a characterization given by Harary and Norman for linedigraphs. It is also possible to repeatedly contract vertices of the line-digraph (with a new contraction procedure) so as to obtain the digraph derived from D by deleting all vertices with no incoming edges. Several new identities for arborescences are presented, leading to a combinatorial proof of Knuth's formula for the number of arborescences of a line-digraph. A new proof is given for the fact that in a digraph with every vertex having indegree equal to outdegree, the number of arborescences with root Vj is independent of j. Finally a new proof is presented for Tutte's Matrix Tree Theorem which shows the theorem to be a special case of the principle of inclusion-exclusion