Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer 1

up vote 2 down vote accepted

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$ .

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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