Connected digraph, the rank $M=V-1$

Question

As shown above, how to prove the rank of the incidence matrix is $V-1$? First, I figure out that the incidence matrix of a digraph will have 1 or -1 (and zero also) in each column (that are edges). Then, from this fact, I prove that the column vectors in $M$ are linearly dependent, so, rank $M < V$ and thus, rank $M \leq V-1$. But suddenly i realize that the digraph is just "connected". It is possible to exist an edge with only connect to one vertex. Then the above proof and logic are wrong. Those are only suitable to use in a digraph iff it contains "cycle". Is it the case?? How can go further to this question

Answer 1

You are right that a linear dependence between columns of the incidence matrices comes from cycles. However, a linear dependence between columns isn't what you're looking for, anyway. The number of columns is $E$, the number of edges; if the columns are linearly dependent, then the rank is less than $E$; however, $E$ may be much larger than $V$, so this doesn't necessarily help.

Instead, you should be looking for a linear dependence between rows of the incidence matrix. By default, the rank of the matrix is at most $V$, the number of vertices (and therefore the number of rows). If you find a dependence between the rows, then the rank of the matrix is at most $V-1$.

To start off, you should observe that the sum of the rows of the incidence matrix is $0$. This guarantees that the matrix is has rank at most $V-1$. Then, convince yourself that in a connected graph, this is the only linear dependence between the rows.