A basis for the cut space C* of a graph I'm reading Diestel's Graph Theory right now and came across an interesting exercise that I cannot solve. It has to do with the basis for the cut space $C^*$:
Given a graph $G$, find among all cuts of the form $E(v)$ a basis for the cut space of $G$, $C^*$.
I know that the space $C^*$ is generated by cuts of the form $E(v)$, $v ∈ V(G)$, but which cuts precisely are they?
 A: Consider the node-arc incidence matrix $A$ for your graph $G(V, E)$, $|V|=n$, $|E|=m$. (I will now assume that your graph is directed and connected.) Initially, $A$ is an $n \times m$ matrix (a row for each node and a column for each arc), with $1$ in the position $(v,e)$ if node $v$ is the head of arc $e$, $-1$ in the position $(v,e)$ if node $v$ is the tail of arc $e$, and zero otherwise. Usually, we assume that an arbitrary row of $A$ is deleted.
The following claims hold:


*

*$A$ is of full ($n-1$) row rank;

*for any set of $(n-1)$ linearly independent columns of $A$, the arcs corresponding to these columns make up a spanning tree of $G$;

*the null-space of the linear transformation $A$ is called the cycle space of $G$ and it is of dimension $m-n+1$ (the cyclomatic number of $G$);

*a basis for the cycle space is obtained as follows: for any spanning tree $T$ of $G$, each out-of-tree arc $(i,j)$ creates a unique cycle if arc $(i,j)$ is concatenated to the unique in-tree $j\to i$ (undirected) path and there are exactly $m-n+1$ such cycles;

*a simple way to obtain a cycle basis is to reorder the columns of $A$ to obtain the form $A=[B\quad N]$, where $B$ is an $(n-1)\times(n-1)$ submatrix of $A$ (recall, the columns correspond to a spanning tree), and then 
$$\begin{pmatrix}-B^{-1}N\\I_{m-n+1}\end{pmatrix}$$ 
is a cycle basis where $I_{n-1}$ is the identity matrix of size $m-n+1$;

*the orthogonal subspace of the cycle space is called the cut space and it is of dimension $m - d_{\text{null space}} = n-1$;

*a basis for the cut-space is obtained as follows: for any spanning tree $T$ of $G$, any in-tree arc $e$ creates a unique cut of $G$ with some properly chosen set of out-of-tree arcs, and the incidence vectors of these cuts are linearly independent;

*a simple way to obtain a cut basis is again to write $A=[B\quad N]$ where $B$ is a $(n-1)\times(n-1)$ basis and then
$$\begin{pmatrix}I_{n-1} & B^{-1}N\end{pmatrix}$$ 
is a cut basis where $I_{n-1}$ is the identity matrix of size $n-1$

*you can check that the bases are indeed orthogonal by verifying that
$$\begin{pmatrix}I_{n-1} & B^{-1}N\end{pmatrix}\begin{pmatrix}-B^{-1}N\\I_{m-n+1}\end{pmatrix}=0$$
The proofs of the above claims can be found in the excellent textbook:
Norman Biggs: "Algebraic Graph Theory", Cambridge Mathematical Library, 1994
