In discussion of a lemma in the paper "Minimum cuts and shortest homologous cycles" Chambers Erickson and Nayyeeri make the claim that an even subgraph of an embedded graph can be decomposed into a union of weakly simple cycles but may not be able to be decomposed into a union of simple cycles. Does anyone know an example of an embedded graph that is like this?

Some definitions from the paper in case they are not standard:

A path in a surface $\Sigma$ is a continuous function $p\colon [0,1]\to \Sigma$. A path is simple if the function that defines it is injective. A cycle is a continuous function $\gamma \colon S^1\to\Sigma$.

An embedding of an undirected graph $G$ on a surface consists of a mapping of vertices of $G$ to distinct points in $\Sigma$ and a collection of mappings from edges of $G$ to simple paths in $\Sigma$ that intersect only at common endpoints.

Two paths in a combinatorial surface cross if no continuous infinitesimal perturbation makes them disjoint; if such a perturbation exists, then the paths are non-crossing. We say that a cycle $\gamma$ is non-self-crossing if no two sub-paths of $\gamma$ cross, weakly simple if $\gamma$ is non-self-crossing and traverses each edge at most once, and (strictly) simple if $\gamma$ visits each vertex at most once.

An even subgraph is a subgraph of $G$ in which every node has even degree, or equivalently, the union of edge-disjoint cycles

We define a cycle decomposition of an even subgraph $H$ to be a set of edge-disjoint, non-crossing, weakly simple cycles whose union is $H$.

Lemma 3.2. Every even subgraph of an embedded graph has a cycle decomposition.


1 Answer 1


The answer to this is embarrassingly easy. The key is the 'non-crossing' condition in the definition of a cycle decomposition. Imagine a graph embedded on the torus with one vertex and two edges, each going around a different hole in the torus. This is weakly simple because we can go around it without crossing our path but it can't be further decomposed.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .