A Proof of Tuite’s Trinity Theorem and a New Determinant Formula

Abstract

A new proof of Tutte’s trinity theorem (Proc. Cambridge Phil. Soc., 1948), (North-Holland, 1973) is presented. The proof is based on a new determinant formula for the number of spanning arborescences of a digraph. This formula generalizes the determinant formula given by Maurer (SIAM J. Appl. Math., 1976) for the number of spanning trees of an undirected graph.