Let $G$ be a graph with $n$ vertices, and let $B_G$ be its incidence matrix. Show that:

If $G$ is a tree (a connected graph without cycles) then the rank of $B_G$ is exactly $n-1$.

I try to use that a tree always has some vertex of degree one, but I don't get it.

  • $\begingroup$ I suggest you try drawing some small trees and writing down their incidence matrices to get a feel for what's going on. $\endgroup$ – Tara B Feb 23 '13 at 12:50

The statement in this form might be a little misleading. In general, if $G$ is any connected graph, then the rank of its incidence matrix is $n-1$. To see this, look at the rows of $B_{G}$ as vectors with entries mod $2$. The sum of these vectors is $0$ because the sum is just the sum of all columns, and each column has only two $1$ entries. This gives that the vectors can't be linear independent so the rank is $ \leq n-1$. For $\geq n-1$, just see what it means for the graph to be connected in terms of the incidence matrix. Take the linear combinations of any $k$ vectors among the rows and check that the sums can't be $0$ .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.