Let $G$ be a graph embedded on an orientable compact surface of genus $g$ so that the embedding is cellular. Consider the dual of the graph $G^*$. Let $C_1$ and $C_2$ be disjoint cycles in $G^*$ that are homotopic to each other and let $E_1$ and $E_2$ be their corresponding edge sets in $G$ respectively. Is $G \setminus (E_1 \cup E_2)$ a disconnected graph?


Yes. Let me write $\Sigma$ for the surface on which $G$ and $G^*$ are embedded.

Because the cycles $C_1$ and $C_2$ are homotopic, they are also in the same $\mathbb{Z}_2$-homology class. So by definition, the symmetric difference $C_1\oplus C_2$ is the boundary of the union of some subset of faces of $G^*$; call this union of faces $U$. (In fact, either $U$ or its complement $\Sigma\setminus U$ must be an annulus, but this isn't important.)

Because $C_1$ and $C_2$ are disjoint, the symmetric difference $C_1\oplus C_2$ is equal to the union $C_1\cup C_2$. In particular, we have $C_1\oplus C_2\ne \varnothing$, which implies that both $U$ and its complement $\Sigma\setminus U$ are non-empty. In other words, the subsurface $\Sigma \setminus (C_1\cup C_2)$ is disconnected.

Any path in $G$ can be viewed as a path in $\Sigma$ that avoids the vertices of $G^*$, and vice versa (up to homotopy). Thus, the (graph) components of $G\setminus (E_1\cup E_2)$ correspond bijectively to the (surface) components of $\Sigma \setminus (C_1\cup C_2)$. We conclude that $G\setminus (E_1\cup E_2)$ is disconnected.

The assumption that $\Sigma$ is orientable is never used.

  • $\begingroup$ Jeff, can you point me to a reference which contains this result? $\endgroup$
    – user1694
    Apr 7 '12 at 4:40
  • 2
    $\begingroup$ Sorry, no. But the observation that two simple disjoint homotopic non-contractible cycles bound an annulus (which gets you most of the way there) appears in David B. A. Epstein. Curves on 2-manifolds and isotopies. Acta Mathematica 115:83–107, 1966. $\endgroup$
    – Jeffε
    Apr 7 '12 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy