Let $G$ be a connected graph with n vertices. Suppose a subset $S$ ⊂ $E(G)$ with $|S| = n − 1$ defines a spanning tree in G. Let $Q_S$ be the restriction of the incidence matrix $Q$ of $G$ to the columns indexed by $S$. Show that $Qˆ{ _S} = Q_S− (\text{a row})$ is invertible by constructing the inverse.
Proof
Since spanning tree has just one connected component, its rank of incidence matrix is $n-1$. This is given by the following theorem
If $G$ is a connected graph on $n$ vertices,then rank $Q(G) = n−1$
Now since $\hat Q{_s}$ is $n-1$ x $n-1$ matrix and its rank is $n-1$, it's invertible.