Return to Revisions

The rank of the incidence matrix is $|V|$ minus the number of bipartite components. I assume the graph is connected. If it is not bipartite, it follows that the row space is $\mathbb{R}^{V}$ and hence it contains the all-ones vector. If the graph is bipartite, the vector that is 1 on the vertices in the first colour class and $-1$ on the other is orthogonal to each row. So the row space is the orthogonal complement to this vector, and therefore it contains the all-ones vector.