Mac Lane's Planarity Criterion Proof

114 Views Asked by At

Given a graph $G$, we denote $\mathcal{C}(G)$ its cycle space. We say that a basis $B$ of $\mathcal{C}(G)$ is a $2$-basis if every element of $B$ is a cycle and every edge of $G$ belongs to at most two of these cycles. I need to prove the following implication of Mac Lane's planarity criterion:

Let $G$ be a planar graph. Then $\mathcal{C}(G)$ has a $2$-basis.

I've looked for a proof in books and articles, but I couldn't find anything convincing. They're either restricting the hypotheses or giving the result for granted. I've read one should pick as elements of the $2$-basis the boundaries of the faces of $G$, but these are not necessarily cycles! One can easily find an example in which the boundary of a face is not a cycle.

My idea to overcome this is to observe that the boundary of a face $f$ decomposes $\mathbb{R}^2 \setminus \partial f$ in $k+2 \geq 2$ connected components, one of which is $f$, one is unbounded and not interesting for me, whereas the other components contain some subgraphs $H_1,\dots,H_k$ of $G$. We do not consider $\partial f$ when constructing a $2$-basis, but rather the symmetric difference of $\partial f,\partial f_1,\dots,\partial f_k$, where $f_1,\dots,f_k$ are the external faces of $H_1,\dots,H_k$ considered as standalone graphs, not as subgraphs of $G$, but with the same embedding in the plane. In the previous photo, we have an example with $k=1$.

This idea however is driving me crazy since proving that the boundary of $f$ induces such a decomposition of the plane is not trivial at all (yes, this is where my recent questions Possible corollary of Jordan's curve theorem and Corollary of Jordan's curve theorem, generalized come from). This is why I am asking you to please provide me with a working proof, or at least a reference, with a cleaner approach.