Problem 1118

Prove that conclusion (i) follows from Lemma 6.5.1 (i) and the fact that $\vec{e} \mapsto \vec{e} *$ is a bijection.
For the necessity part of (ii), we assume that $g$ is a flow on $G^{*}$ and consider a given orientation of a cycle $C \subseteq G$. Let $F:=E(C)$. By Proposition 4.6.1, $F^{*}$ is a minimal cut in $G^{*}$, i.e., for some appropriate $X \subseteq V^{*}$, we have $F^{*}=E^{*}(X, \bar{X})$. According to the definitions of $f$ and $g$, for one of the two orientations $\vec{C}$ of $C$, by Lemma 6.5.1 (ii) and Proposition 6.1.1, we get
$$f(\vec{C})=\sum_{\vec{e} \in \vec{C}} f(\vec{e})=\sum_{\vec{d} \in \vec{E}^{*}(X, \bar{X})} g(\vec{d})=g(X, \bar{X})=0.$$

Thus, according to $f(\overleftarrow{C})=-f(\vec{C})$, for the given orientation of $C$, the corresponding value must also be zero.
For the sufficiency part, according to (i), we only need to prove that $g$ satisfies (F2). Here, we will prove a more general result: for every cut $F^{*}=E^{*}(X, \bar{X})$ of $G^{*}$, we have $g(X, \bar{X})=0$. By Lemma 1.9.3, we can assume that $F^{*}$ is in fact a bond of $G^{*}$. Since $G$ and $G^{*}$ are connected, $F$ is the edge set of a cycle $C \subseteq G$ (Proposition 4.6.1). According to Lemma 6.5.1 (ii), $C$ has an orientation $\vec{C}$ such that $\{\vec{e} * \mid \vec{e} \in \vec{C}\}=\overrightarrow{E^{*}}(X, \bar{X})$. Therefore, according to the definitions of $f$ and $g$, we have $g(X, \bar{X})=f(\vec{C})=0$.

With the help of Lemma 6.5.2, we can now prove the coloring-flow duality theorem for planar multigraphs. Let $P=v_{0} \ldots v_{\ell}$ be a path with edges $e_{i}=v_{i} v_{i+1} (i<\ell)$, then we denote (depending on the labeling of the vertices on $P$)
$$\vec{P}:=\left\{\left(e_{i}, v_{i}, v_{i+1}\right) \mid i<\ell\right\},$$

and call $\vec{P}$ a $v_{0} \rightarrow v_{\ell}$ path $\left(v_{0} \rightarrow v_{\ell}\right.$ path $)$. Similarly, $P$ is implicitly given by $\vec{P}$.