Lesson 13

Call a subgraph even if every vertex has even degree in it.

Lemma. A graph has a nowhere-zero \(2^{p}\)-flow if and only if its edge set can be covered by \(p\) even subgraphs \(F_{1},…,F_{p}\).

Proof. We will work over \(\mathbb{Z}^{p}_{2}\). Suppose first that \(F_{1},…,F_{p}\) are even subgraphs whose union contains every edge. For an edge \(e\), define a vector \(\phi(e)\in\mathbb{Z}_{2}^{p}\) by putting the \(i\)-th coordinate equal to \(1\) exactly when \(e\in F_{i}\). Because every edge belongs to at least one \(F_{i}\), this vector is never zero. For each coordinate \(i\), every vertex is incident to an even number of edges of \(F_{i}\), which is exactly the conservation law over \(\mathbb{Z}_{2}\). So \(\phi\) is a nowhere-zero \(\mathbb{Z}_{2}^{p}\)-circulation.

Conversely, let \(\phi\) be a nowhere-zero \(\mathbb{Z}_{2}^{p}\)-circulation. For each coordinate \(i\), let \(F_{i}\) be the set of edges whose \(i\)-th coordinate is \(1\). Conservation over \(\mathbb{Z}_{2}\) says that every vertex has even degree in \(F_{i}\). Since \(\phi(e)\) is never the zero vector, every edge belongs to at least one of the \(F_{i}\).◼