Lecture series on graph theory 8

Proof of the coloring-flow duality theorem

$\Rightarrow$ Assume that G is face k-colorable (proper coloring)

We need to show that G has a nowhere-zero k-flow $(D,f)$

$$\begin{aligned} (i.e. &f:E(G)\to\{-(k-1),-(k-2),\cdots,-1,1,\cdots,k-2,k-1\}\\& s,t,\forall v\in V(G),\sum_{e\in E^{+}(v)}f(e)=\sum_{e\in E^{-}(v)}f(e)) \end{aligned}$$

Let $F(G)$ be the set of all faces of G and let $c:F(G)\to[k]$ be a face coloring.

Assign an orientation $D$ to $E(G)$: each edge $e\in E(G)$ is oriented such that the face with a smaller color index is on the right side of the arc.

Define a function $f:E(G)\to[k-1]$ such that $f(e)$ is the absolute value of the difference of the colors of two faces incident with e.

**claim: $(D,f)$ is a nowhere-zero k-flow**

---

Proof of claim:

Clearly, $0 Let v be vertex of G and $v_1,v_2,\cdots,v_d$ be all neighbors of v appearing around v in a clockwise order.Let $f_i$ be the face containing edges $vv_1$ and $vv_{i+1}$ . Note that, for any $i\not=j,f_i\not=f_j$ because G is 2-connected. Define $$ \textcolor{blue}{\epsilon_i=\left\{\begin{aligned}&-1,\quad if\ v\to v_i\ in\ D\\&1,\quad if\ v_i\to v\ in\ D \end{aligned}\right.} $$ Then, for each $i\in[d]$ $$ \textcolor{blue}{c(f_i)=c(f_d)+\sum_{j=1}^i\epsilon_if(vv_j) \tag{*}} $$  $$ \begin{aligned}&\textcolor{blue}{c(f_1)=c(f_d)}+\textcolor{red}{f(vv_1)}\\&\textcolor{blue}{c(f_2)=c(f_1)-f(vv_2)=c(f_d)+f(vv_1)-f(vv_2)=c(f_d)+\sum_{j=1}^2\epsilon_jf(vv_j)}\end{aligned} $$ From (*), $c(f_i)=c(f_d)+\sum_{j=1}^i\epsilon_if(vv_j)$. It follows that $$ \textcolor{blue}{\sum_{j=1}^d\epsilon_jf(vv_j)=0\Rightarrow\sum_{e\in E^{+}(v)}f(e)=\sum_{e\in E^{-}(v)}f(e)} $$ --- $\Leftarrow$ Assume that G has a nowhere-zero k-flow $(D,f)$. Define a map $c:F(G)\to\{1,2,\cdots,k-1\}$ Choose an arbitrary face $f_0$ and let $c(f_0)=1$. For each arc $e_i$ in D, let $f_i'$ and $f_i''$ be two faces incident with $e_i$. If one of $f_i'$ and $f_i''$ is colored, then the color of another face is given by the following equality $$ c(f_i'')=c(f_i')+f(e_i)(mod\ k) $$ It suffices to show that the vertex coloring is well-defined.In other words, the process does not color one face by two or more different colors.

Let $f_1$ be uncolored face incident with two colored faces $f_2$ and $f_3$.Let $e_i$ be the edge on the boundary of $f_1$ and $f_i$ for $i=2,3$. Without loss of generality, let $f_i$ be on the left side of the arcs $e_2$ and $e_3$.

**claim: $c(f_2)+f(e_2)\equiv c(f_3)+f(e_3)(mod\ k)$**

---

**Proof of claim:**

Consider the dual graph $G^\star$ of G. The vertex subset $X^\star=\{f\in V(G^\star)\big|f\in F(G)\ is\ colored\ already\}$ induces a connected subgraph of $G^\star$. Thus, there is a cycle $C^\star$ of $G^\star$ containing $f_1,f_2$ and $f_3$.The cycles $C^\star$ also contains the edge $f_1f_2$ and$f_1f_3$, $V(C^\star)\backslash \{f_1\}\subset X^\star$. Since all edges of G corresponding to the edge of $C^\star$​ separate G into two parts (i.e. these edges form an edge-cut), Let X be the set of vertices in one part. It follows from a lemma that $$ \textcolor{blue}{\sum_{e\in E^{+}(v)}f(e)-\sum_{e\in E^{-}(v)}f(e)=0} $$ So the clain follows.

---

This completes the whole proof.

Recall: Every Eulerian graph G has a cycle decomposition: edges of G can be decomposed into edge-disjoint cycles.

A cycle cover of a graph is a family of cycles which cover all edges of G.

A graph has a cycle cover $\Leftrightarrow$ it has even-subgraph cover.

Thm If a graph G has k-even-subgraph cover, then G has a nowhere-zero $2^k$-flow

---

Proof

For each even-subgraph $H_i$, it has a 2-flow $(D,f_i)$.

So $(D,f)$ is a nowhere-zero $2^k$-flow where $f=\sum_{e\in E(G)}2^{i-1}f_i(e)$

---

(8-flow theorem,Jaeger) Every bridgeless graph has nowhere-zero 8-flow

(Splitting Lemma) Let G be a connected graph without cut-edge.If G has a vertex v of degree at least four. Then there are two edges $e_1$ and $e_2$ incident with v s.t. the resulting graph after splitting $e_1$ and $e_2$ from v remains to be connected and without cut-edge.

(Cycle double cover conjecture,1970s) Every connected cubic graph without cut-edge has a family of cycles covering every edge exactly twice.

A proper k-edge-coloring of a graph G is a map $c:E(G)\to[k]$ s.t. $c(e)\not=c(e’)$ if $e$ and $e’$ have a common end vertex.

Thm Every 3-edge-colorable cubic graph has a family of cycles which cover every edge exactly twice

---

Proof

Let $c:E(G)\to[3]$. Then $c^{-1}(1)\cup c^{-1}(2)$ is a family of cycles, $c^{-1}(1)\cup c^{-1}(3)$ is a family of cycles, $c^{-1}(2)\cup c^{-1}(3)$ is a family of cycles.

$$l_{e_1}=c^{-1}(1)\cup c^{-1}(2),l_{e_2}=c^{-1}(1)\cup c^{-1}(3),l_{e_3}=c^{-1}(2)\cup c^{-1}(3)$$

So $l{e_1}\cup l{e2}\cup l{e_3}$ is a family of cycles which cover every edge exactly twice.

---

(3-flow conjecture) Every 5-edge connected graph has a nowhere-zero 3-flow. A graph is a k-edge-connected if for any two vertices x ang y, the graph has k edge-disjoint paths joining x and y. (Tutte-Nashwillam Theorem) Every 2k-edge-connected graph has a k edge-disjoint spanning trees. (Lovasz,Wu,Thomassen,Zhang,2012) Every 6-edge-connected graph has a nowhere-zero 3-flow. (5-flow conjecture.1950s) Every bridgeless graph has a nowhere-zero 5-flow (Seymour,1980) Every bridgeless graph has a nowhere-zero 6-flow. For cubic graph,cycle double cover conjecture$\approx$ the strong embedding conjecture (Strong Embedding Conjecture,1980s) Every 2-connected graph can be embedded on a closed surface such that every face is bounded by a cycle.