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

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.

• I suggest you try drawing some small trees and writing down their incidence matrices to get a feel for what's going on. – 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$ .