Linear Spaces of a Graph, Part 3

When are Z and B disjoint?

How to contact me.
This material comes from some notes for a University of Waterloo course taught by Herb Shank. (c. 1975)
Back to Part 1.
Back to Part 2: Resistive Networks.

Back to the Graph Theory Index.
As another application of Theorem 3, we investigate whether Z and B are disjoint. If they are, then by adding dimensions, we have immediately that C is the direct sum of Z and B. It turns out that whether Z and B are disjoint depends on the relation of the number N of spanning trees to the characteristic of the field F.
Theorem 5. ZF(G) and BF(G) are disjoint if and only if N(G) is not a multiple of the characteristic of F. Moreover, if Z and B are disjoint, the projection on C onto Z is N -1(AT1 + AT2 + ...) and that of C onto B is N -1(BT1 + BT2 + ...).

Proof. By Theorem 3, using R=I, we know that AT1 + AT2 + ... = AT1* + AT2* + ...

Suppose that N is not zero in F. Note that each AT is the identity on Z and each AT* sends cocyles to zero (the rows of the matrix representing AT* are the columns of the matrix representing AT and are thus cycles, which by definition have inner product zero with any cocycle). Thus, N -1(AT1 + AT2 + ...) preserves cycles and sends cocyles to zero. For the projection expression for B, use the above and Lemma 6: AT + BT* = I.

The following proof of the converse is due to S. Maurer: Suppose that N is zero in F. It could happen that (AT1 + AT2 + ...)c is non-zero for some c. If so, then (AT1 + AT2 + ...)c + (BT1 + BT2 + ...)c = Nc = 0, so that (AT1 + AT2 + ...)c = -(BT1 + BT2 + ...)c is a non-zero member of Z(G) intersect B(G). Otherwise, AT1 + AT2 + ... is the zero linear transform and, in particular, for an edge e ( (AT1 + AT2 + ...)e , e ) = 0. Since this is the number of spanning trees of G not containing e, N(G-e)=0 and, by Lemma 3 and Corollary, N(Ge )=0. By induction of the number of edges, there is some non-zero d1 in Z(G-e) intersect B(G-e) and some non-zero d2 in Z(Ge ) intersect B(Ge ). By Lemma 4 and Lemma 5,

d1 in Z(G), d2+k2e in Z(Ge ) and
d2 in B(G), d1+k1e in B(Ge ).

If k1=0, then d1 is in Z(G) intersect B(G).
If k2=0, then d2 is in Z(G) intersect B(G).
Otherwise, (k1-1d1+e) + k2-1d2 is in B(G) and (k2-1d2+e) + k1-1d1 is in Z(G).
Back to the
Graph Theory Index.
Department of Mathematical Sciences
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991

Office: Room 286, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436

Last modified November 3, 2000, by S.C. Locke.