<p>I assume that you require that all faces of <span class="math-container">$G$</span> are topological disks. After cutting along <span class="math-container">$C^*$</span>, each face is a topological disk bounded by either a cycle of <span class="math-container">$G$</span>, or a cycle that consists of two arcs (one on <span class="math-container">$G$</span> and one on <span class="math-container">$C^*$</span>) with common endpoints (at the intersection between edges of <span class="math-container">$C$</span> and their duals), where the arc on <span class="math-container">$C^*$</span> lies on the boundary of the cut surface. In particular, the boundary of any face intersects <span class="math-container">$G$</span> in a single component.</p>
<p>Now, assume for a contradiction that the surface after cutting is still connected, and consider an edge <span class="math-container">$(u,v)\in C$</span>. Then there exists a path <span class="math-container">$\pi$</span> on the cut surface connecting <span class="math-container">$u$</span> and <span class="math-container">$v$</span>. By the above property of faces, we can snap <span class="math-container">$\pi$</span> to a path on <span class="math-container">$G-C$</span>, showing that <span class="math-container">$u$</span> and <span class="math-container">$v$</span> lie in the same component of <span class="math-container">$G-C$</span>. Therefore, <span class="math-container">$C-(u,v)$</span> is still an edge cut for <span class="math-container">$G$</span>, contradicting minimality of <span class="math-container">$C$</span> and hence connectedness of the cut surface.</p>

CC BY-SA 4.0
2022-09-28T05:35:15.677Z
2022-09-28T11:59:53.460Z
2022-09-28T11:59:53.460Z
Tim
<p>Let <span class="math-container">$G$</span> be a graph that embedded on a surface of genus <span class="math-container">$g$</span>, moreover the embedding is triangulated. Let <span class="math-container">$C$</span> be a collection of edges that forms a minimal edge cut for <span class="math-container">$G$</span>. Let <span class="math-container">$C^*$</span> consist of the dual edges for edges in <span class="math-container">$C$</span>. <span class="math-container">$C^*$</span> consists of vertex disjoint cycles in the dual <span class="math-container">$G^*$</span>. How do we prove that cutting along the cycles in <span class="math-container">$C^*$</span> disconnects the surface? This holds for planar graphs by the Jordan curve theorem.</p>

<reference-request><graph-theory><topological-graph-theory>
Dual of cut of embedded graph disconnects surface
SamiD
# Dual of cut of embedded graph disconnects surface

(Asked by: username_0 on 2022-09-25)

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.

**Tags:** reference-request, graph-theory, topological-graph-theory

---

## 1 answers

### Answer by username_1 on 2022-09-28. Score: 4 | Accepted answer

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.


---

