Readers are referred to Appendix C for definitions and fundamental properties in the integer flow theory.

In this chapter, we present some results about circuit cover problems directly resulting from and related to integer flow theory.

**Theorem 8.1.1** (Matthews [174]) *Let r be a positive integer. A graph G admits a nowhere-zero 2 ^{r}-flow if and only if G has an r-even subgraph cover*.

*Proof* “⇒”: Induction on *r*. By Theorem C.2.3, let (*D*,*f*_{1}) be a 2^{r-1}-flow of *G* and (*D*, *f*_{2}) be a 2-flow of *G* such that *supp*(*f*_{1}) ∪ *supp*(*f*_{2}) = *E*(*G*). By the inductive hypothesis, *supp*(*f*_{1}) is covered by even subgraphs {*C*_{1},…, *C*_{r–1}}. Thus, {*C*_{1},…, *C*_{r–1}, *C _{r}*} is an

Start Free Trial

No credit card required