Mathematics — Graph Theory · spanning-trees-even-parity
Problem
Let G be a multigraph with an even number of vertices. Assume that each vertex of G has an even degree. Prove that G has an even number of spanning trees.
[Hint: First show a lemma: Let n∈N be odd. Let B be an n×n-matrix with integer entries. Assume that B is symmetric (i.e., satisfies BT=B), and that all diagonal entries of B are even. Then, detB is even.]