Cuts and Flows

Let X be a graph with an orientation σ and let D be the incidence matrix of Xσ. In this chapter we continue the study of how graph-theoretic properties of X are reflected in the algebraic properties of D. As previously, the orientation is merely a device used to prove the results, and the results themselves are independent of which particular orientation is chosen. Let ℝE and ℝv denote the real vector spaces with coordinates indexed by the edges and vertices of X, respectively. Then the column space of DT is a subspace of ℝE, called the cut space of X. The orthogonal complement of this vector space is called the flow space of X.