0
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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