Let

For example, if

1 1 1 0 0 0 -1 0 0 1 1 0 0 -1 0 -1 0 1 0 0 -1 0 -1 -1The particular matrix obtained depends on the orderings and the orientations chosen. In any case, the column sums are zero, the sums of the absolute values of the entries in each column are two, the sums of the absolute values of the entries in each row are the degrees of the vertices.

If a graph

It is sometimes convenient to work with some field

Two graphs

A second matrix obtained from the graph is the

The group of isomorphisms from a graph

One can consider the Petersen graph,

Now, consider any path in the Petersen graph,

Now, since rank

Similarly,

We need only show that this common entry is the number of spanning trees of

Now (by the Binet-Cauchy theorem): det

Thus, det

There is a slightly more general versison of the Matrix-Tree Theorem. Label the edges of the graph,

It is obvious that setting

Let

Now (by the Binet-Cauchy theorem): det

We verify the statement of the Binet-Cauchy theorem. (Following the proof in van Lint and Wilson.)

Now,

Then,

Now, replace all indeterminants in

For much more about algebraic properties of graphs, read the book

Florida Atlantic University

777 Glades Road

Boca Raton, Florida 33431-0991

USA

**
Office: Room 286, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436
LockeS@fau.edu
URL: http://math.fau.edu/locke/graphmat.htm
**

Last modified May 3, 1999, by S.C. Locke.