2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.