Cycles and spanning trees (Q1179106): Difference between revisions

Given a connected graph \(G\), it is shown that the number of labelled spanning trees of \(G\) is equal to the determinant of a cycle-cycle incidence matrix. Using this cycle-based approach, it is seen that the graph of a convex polyhedron and its dual have the same number of spanning trees. The method can also be used to show that certain sequences of algebraic numbers can be represented by a recursive formula using only integers.