# Integer flows and cycle covers of graphs

### Cun-Quan `C. Q.' Zhang

#### New York, NY 10016

Please send suggestion and comments to C. Q. Zhang

## Contents

```Preface                                                         v
Integer Flows                                                   1
Chapter 1       Introduction to Integer Flows           3
1.1     Definitions and Tutte's conjectures             3
1.2     Elementary properties of flows          5
1.3     Modular flows           9
1.4     Flows and face colorings                12
1.5     Exercises               21
Chapter 2       Basic Properties of Integer Flows               25
2.1     Product of flows                25
2.2     Group flows             27
2.3     Bounded orientations            28
2.4     Cycle covers            30
2.5     Orientable cycle double cover   33
2.6     Sum of flows            35
2.7     Flow polynomial         37
2.8     Minimal counterexamples         38
2.9     Exercises               45
Chapter 3       Nowhere-Zero 4-Flows            49
3.1     Cycle covers and 4-flows                50
3.2     Parity subgraph decompositions          51
3.3     Evenly spanning cycles          53
3.4     4-edge-connected graphs         58
3.5     Faithful cycle covers           59
3.6     Orientable cycle double covers          62
3.7     Snarks          63
3.8     Collapsible graphs              76
3.9     Beyond the 4-color theorem              81
3.10    Exercises               84
3.11    Open problems           90
Chapter 4       Nowhere-Zero 3-Flows            93
4.1     Modular 3-orientations          93
4.2     Orientable cycle double covers          95
4.3     Weak 3-flow conjecture          96
4.4     3-color theorems                98
4.5     Exercises               106
4.6     Open problems           107
Chapter 5       Nowhere-Zero \$k\$-Flows (k ³ 5)          109
5.1     5-color theorem         110
5.2     8-flow theorem          112
5.3     6-flow theorem          114
5.4     Structure of 6-flow             117
5.5     Exercises               119
5.6     Open problems           121

Cycle Covers                                                    123
Chapter 6       Faithful Cycle Covers           125
6.1     Introduction            125
6.2     Minimal contra-pairs            127
6.3     Circuit chain           128
6.4     Petersen graph and faithful covers (I)          132
6.5     Petersen graph and faithful covers (II)         133
6.6     Admissible dipath               137
6.7     Planar graphs and faithful covers               140
6.8     Fractional faithful cover       144
6.9     Exercises               146
6.10    Open problems           150
Chapter 7       Cycle Double Covers             153
7.1     Double covers and graph embeddings              153
7.2     Minimal counterexamples         155
7.3     Cycle 2k-covers         159
7.4     Five cycle double covers                162
7.5     Small circuit double covers             168
7.6     Exercises               169
7.7     Open problems           171
Chapter 8       Shortest Cycle Covers           175
8.1     Postman tour and shortest cover         175
8.2     Shortest cover and 4-flow (I)           180
8.3     Shortest cover and 4-flow (II)          183
8.4     Shortest cover and 8-flow (I)           184
8.5     Shortest cover and 8-flow (II)          188
8.6     Shortest cover and 6-flow               190
8.7     Shortest cover and 5-flow               197
8.8     Shortest cover and double cover         200
8.9     NP-completeness         204
8.10    Exercises               208
8.11    Open problems           210

Related Topics                                          213
Chapter 9       Generalization and Unification          215
9.1     Circular double covers          215
9.2     Modular orientation             216
9.3     Fractional flows                220
9.4     Cycle space minors              221
9.5     Group connectivity              223
9.6     Exercises               228
9.7     Open problems           231
Chapter 10      Compatible Decompositions               233
10.1    Introduction            233
10.2    Minimal contra-pairs            237
10.3    Planar graphs           242
10.4    \$K_5\$-free graphs               243
10.5    Forbidden system reduction              248
10.6    Exercises               258
10.7    Open problems           261
Chapter 11      Related Topics          263
11.1    Unique edge-3-coloring          263
11.2    Depth of circuit cover  268
11.3    Removable circuits              270
11.4    Even circuit decomposition              275
11.5    Exercises               276
11.6    Open problems           279

Appendices              281
A       Fundamental Theorems            283
A.1     Some basic theorems             283
A.2     Edge-disjoint spanning trees            286
A.3     Cover by perfect matchings              290
A.4     Excluding Petersen minor        293
A.5     Vertex splitting                296
A.6     Exercises               299
A.7     Open problems           300
B       Hints for Exercises             303
C       Notations and Terminology               337

Bibliography                            353

Index                                   373

```