2
$\begingroup$

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

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

I think that the rank of incidence matrix of a connected graph with n vertices is not always n-1. For instance, the rank of a graph which is a cycle of length three is 3 (not equal to n-1).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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