Dark Mode

119 views

1 vote

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?$

- $m-1$
- $m-n+1$
- $\lceil m / 2\rceil$
- $n-1$
- $\lceil n / 2\rceil$