58 views

Let $G$ be a directed graph (with no self-loops or parallel edges) with $n \geq 2$ vertices and $m$ edges. Consider the $n \times m$ incidence matrix $M$ of $G$, whose rows are indexed by the vertices of $G$ and the columns by the edges of $G$. The entry $m_{v, e}$ is defined as follows.

$$m_{v, e}= \begin{cases}-1 & \text { if } e=(v, w) \text { for some vertex } w, \\ +1 & \text { if } e=(u, v) \text { for some vertex } u, \\ 0 & \text { otherwise. }\end{cases}$$

Suppose every vertex of $G$ is reachable from a special source vertex of $G$. Then, what is the rank of $M?$

1. $m-1$
2. $m-n+1$
3. $\lceil m / 2\rceil$
4. $n-1$
5. $\lceil n / 2\rceil$

The rank of the incidence matrix is $(n-1)$, where $n$ is the number of nodes of the graph. So, the answer is option D. $n-1$