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

-

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 order the columns of $A$ so that $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 cycle 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

-