[Math] Rank of an incidence matrix of a graph G with n vertices is n-1 implies that G is connected

Question

I know that when a graph $G$ is connected, it's incidence matrix $A_G$ has rank $n-1$ over $GF(2)$.

However, is it also true that when an incidence matrix $A_G$ has rank $n-1$ that this implies that graph $G$ is connected?

Answer 1

Yes. If $G$ is not connected, let its components be $C_1,\ldots,C_r$ for some $r\ge 2$. For $k=1\ldots,r$ let $M_k$ be the incidence matrix of $C_k$. Then the incidence matrix $M$ of $G$ can be written in the form

$$M=\begin{bmatrix} M_1&0&0&\ldots&0\\ 0&M_2&0&\ldots&0\\ 0&0&M_3&\ldots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\ldots&M_r \end{bmatrix}\;.$$

For $k=1,\ldots,r$ let $n_k$ be the number of vertices in $C_k$; then $M_k$ has rank $n_k-1$, so the rank of $M$ is

$$\sum_{k=1}^r(n_k-1)=n-r<n-1\;.$$