A New Interpretation of the Matrix Tree Theorem Using Weak Walk Contributions and Circle Activation




Robinson, Ellen Beth

Journal Title

Journal ISSN

Volume Title



This thesis provides an alternate proof of the Matrix Tree Theorem by shifting the focus to oriented incidences. We examine the weak walk contributors from the de-terminant of the Laplacian matrix of oriented graphs and classify them according to similar circle structures attained through circle activation. The members of each of these contribution classes form an alternating rank-signed Boolean lattice in which all members cancel. We then restrict our contributors to those corresponding to a given cofactor Lij and demonstrate that those contributors that no longer cancel are in one-to-one correspondence with the spanning trees of the graph. These results allow for possible extension into examining tree-counts in signed graphs and oriented hypergraphs.



graphs, matrix, trees, combinatorics, graph Theory, signed graphs, Honors College


Robinson, E. B. (2015). A new interpretation of the Matrix Tree Theorem using weak walk contributions and circle activation (Unpublished thesis). Texas State University, San Marcos, Texas.


Rights Holder

Rights License

Rights URI