Let $G$ be a graph that embedded on a surface of genus $g$, moreover the embedding is triangulated. Let $C$ be a collection of edges that forms a minimal edge cut for $G$. Let $C^*$ consist of the dual edges for edges in $C$. $C^*$ consists of vertex disjoint cycles in the dual $G^*$. How do we prove that cutting along the cycles in $C^*$ disconnects the surface? This holds for planar graphs by the Jordan curve theorem.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I assume that you require that all faces of $G$ are topological disks. After cutting along $C^*$, each face is a topological disk bounded by either a cycle of $G$, or a cycle that consists of two arcs (one on $G$ and one on $C^*$) with common endpoints (at the intersection between edges of $C$ and their duals), where the arc on $C^*$ lies on the boundary of the cut surface. In particular, the boundary of any face intersects $G$ in a single component.
Now, assume for a contradiction that the surface after cutting is still connected, and consider an edge $(u,v)\in C$. Then there exists a path $\pi$ on the cut surface connecting $u$ and $v$. By the above property of faces, we can snap $\pi$ to a path on $G-C$, showing that $u$ and $v$ lie in the same component of $G-C$. Therefore, $C-(u,v)$ is still an edge cut for $G$, contradicting minimality of $C$ and hence connectedness of the cut surface.
