Incidence matrix proof.

The notation $isim j$ means that vertices $i$ and $j$ are connected by an edge, say $e_k$. Let $q_k$ be the $k$-th column of $Q$. If $isim j$, the only two non-zero entries in $q_k$ are those in rows $i$ and $j$; call them $q_{k,i}$ and $q_{k,j}$, respectively. One of them is $1$, the other is $-1$, and

$$[0]=x'q_k=x_iq_{k,i}+x_jq_{k,j}=q_{k,i}(x_i-x_j),,$$

so $x_i=x_j$.

Now suppose that there is a path $i=i_0sim i_1simldotssim i_ell=j$ from $i$ to $j$. Then

$$x_i=x_{i_0}=x_{i_1}=ldots=x_{i_ell}=x_j$$

by repeated applications of the previous result. $G$ is connected, so there is a path between any two vertices, and therefore $x_1=x_2=ldots=x_n$. Thus, the left null space of $Q$ is either trivial or one-dimensional, and hence $operatorname{rank}Q=n$ or $operatorname{rank}Q=n-1$, respectively. On the other hand, the $n$ rows of $Q$ are sum to a zero vector and are therefore linearly dependent, so $operatorname{rank}Qle n-1$. Combining results, we see that $operatorname{rank}Q=n-1$.