Lesson 2

In this section, we allow loops and parallel edges. For an edge \(e\in E\) we denote by \(G\setminus e\) the graph \(G\) without the edge \(e\), and by \(G / e\) the graph \(G\) with the edge \(e\) contracted. Deletion simply removes \(e\) from the edge set and keeps any parallel edges untouched. Contraction identifies the two endpoints of \(e\) into a single new vertex; any other edge \(e'\) joining the same two endpoints (a parallel edge of \(e\)) now has both of its endpoints merged, so \(e'\) becomes a loop at the new vertex.

Let \(G=(V,E)\) be a directed graph, and let \(\Gamma\) be a finite abelian group. For a vertex \(v\), denote by \(\delta^{+}(v)\) the set of edges leaving \(v\), and by \(\delta^{-}(v)\) the set of edges entering \(v\). A \(\Gamma\)-circulation is a function \(\phi\colon E\to \Gamma\) such that for every vertex \(v\), \[\sum_{e\in\delta^-(v)}\phi(e)=\sum_{e\in\delta^+(v)}\phi(e) \ .\] It is called nowhere-zero if \(\phi(e)\ne 0\) for every edge \(e\).

For example, the network below is a nowhere-zero \(\mathbb{Z}_{5}\)-circulation.

For an undirected graph, we first orient all edges arbitrarily and then use the same definition. The choice of orientation does not matter. Indeed, if we reverse one edge and replace its value by the opposite group element, then the conservation law at its two endpoints remains exactly the same. Also, a loop is incident once to its vertex's incoming side and once to its outgoing side, so conservation places no constraint on its value; in a nowhere-zero circulation, a loop may carry any nonzero group element.