4
$\begingroup$

I am struggling with a problem found in the Graph Theory textbook by Bondy and Murty. The goal is to prove the following result:

Let $G$ be a connected (undirected) graph, and let $M$ be its incidence matrix.

Show that there is a one-to-one correspondence between the bases of the column space of $M$ over $GF(2)$ and the spanning trees of $G$.

This result does not seem right to me, because the two sets in questions don't even have the same cardinality. For instance, if $G$ is a tree on $n$ vertices, it has only one spanning tree, whereas its incidence matrix has dimension $n-1$ over $GF(2)$, and therefore has many bases.

What am I not understanding?


Notations:

  • $GF(2)$ is the field with 2 elements
  • if $G$ is a graph with $n$ vertices and $m$ edges, its incidence matrix is the matrix $M$ with $n$ rows and $m$ columns, with a 1 in cell $(v, e)$ if and only if edge $e$ is a link incident to vertex $v$.
$\endgroup$
5
  • $\begingroup$ Are you sure you have the right definition for "incidence matrix"? It's usually the matrix with $n$ rows and $n$ columns (indexing the vertices) with an entry of $1$ when vertices are joined by an edge.See en.wikipedia.org/wiki/Incidence_matrix $\endgroup$ Nov 19, 2016 at 13:32
  • $\begingroup$ @EthanBolker I am sure. What you are talking about is defined as the "Adjacency matrix" in the book. AFAICT the Wikipedia page you linked to also defines the incidence matrix like the book. $\endgroup$ Nov 19, 2016 at 13:38
  • $\begingroup$ OK I see that distinction in wikipedia. Then I think your counterexample is correct. If I were you I'd try to prove the theorem for the adjacency matrix. I checked it (casually) for a few trees. $\endgroup$ Nov 19, 2016 at 13:59
  • $\begingroup$ I don't think that works either. Consider the adjacency matrix of an n-path: its rank is certainly more than 1, yet a path only has 1 spanning tree. $\endgroup$ Nov 19, 2016 at 14:24
  • $\begingroup$ You're right again. I think I can no longer be of any help. Sorry. $\endgroup$ Nov 19, 2016 at 14:30

1 Answer 1

3
+100
$\begingroup$

I think the key here that the problem is not making clear is that we should be looking for a correspondence between spanning trees of $G$ and bases of the column space of $M$ consisting of columns of $M$.

Let $C$ be the set of columns of $M$ and $E=E(G)$ be the edges of $G$. There is a natural bijection $f:C\to E$ that sends the $k$-th column to the $k$-th edge (or rather sends the column corresponding to $e$ to $e$). This function $f$ induces a bijection $g:\mathcal{P}(C)\to S$ where $\mathcal{P}$ denotes powerset and $S=\{G'\subseteq G\mid V(G')=V(G)\}$ is the collection of all subgraphs of $G$ that have the same vertex set as $G$. Now I claim that $A\in\mathcal{P}(C)$ is linearly independent if and only if $g(A)$ is a forest. It's easier, though, to see that $A$ has a linear dependence if and only if $g(A)$ has a cycle. Given $A\in\mathcal{P}(C)$ with minimal linear dependence $c_1+c_2+\cdots+c_k=0$ (we're working over over $GF(2)$ so we can assume all our coefficients are 1) we see that $f(c_1)$, $f(c_2)$, $\ldots$, $f(c_k)$ form a cycle in $g(A)$. The opposite is also true. Given a graph $H\in S$ with a cycle. We can pull that cycle back to a linear dependence in $g^{-1}(H)$. Finally we just need to say that a maximal linearly independent set is a basis and a maximal forest is a spanning tree to see that $g$ gives a correspondence between bases of the column space of $M$ consisting of columns of $M$ and spanning trees of $G$.

It's good to note that this proof would still essentially work over other coefficient rings. Notably it works with integer coefficient given that you change bases to maximal independent sets and you associate an (arbitrary) orientation to each edge. For the homologically inclined reader I'll also note that the benefit to working with $GF(2)$ coefficients is just that it gives you a very natural correspondence between 1-chains of $G$ (thought of as a 1-dimensional complex) and subgraphs of $G$. And finally that the matrix $M$ is simply the boundary matrix from 1-chains to 0-chains.

$\endgroup$
1
  • $\begingroup$ This makes sense, and is consistent with the way the exercise is laid out. I'm awarding you the bounty. $\endgroup$ Nov 24, 2016 at 19:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .