Graph Theory problem. Prove the following statement.

Question

Problem:

Let $F$ be a minimal edge-cut of a connected multigraph $G=(V,E)$. Prove that there exists a subset $U$ of $V$ such that $F$ is precisely the set of edges that join a vertex in $U$ to a vertex in the complement $\overline U$ of $U$.

Definitions:

1. An edge-cut of $G$ is a set $F$ of edges whose removal disconnects $G$.

2. An edge-cut $F$ is minimal provided that no subset of $F$ other than $F$ itself is an edge-cut.

My Attempt: I am frankly not sure how to approach this problem. It requires an existence proof so do I need to construct a set $U$ or do I need to indirectly show that such a set exists? Any hints will be much appreciated.

Answer 1

Let $U$ be the vertex set of one of the components of $(V,E\setminus F)$.

Minimality of $F$ implies that, for any $e\in F$, the edge set $F'=F\setminus\{e\}$ is not an edge cut. Hence $(V,E\setminus F')$ is a connected graph, while $(V,E\setminus F)=(V,E\setminus F'\setminus\{e\})$ is disconnected. Hence $e$ joins a vertex in $U$ to a vertex in $\overline{U}$.

Now let $e$ be any edge joining a vertex of $U$ to a vertex of $\overline{U}$. That removal of $F$ disconnects $U$ from $\overline{U}$ implies $e\in F$.

We have shown that the set of edges joining a vertex of $U$ to a vertex of $\overline{U}$ both contains and is contained in $F$.

Answer 2

Let $F \subseteq E$ be a minimal edge-cut in $G=(V,E)$. By definition of an edge-cut, the removal of $F$ disconnects $G$ into connected components $G_1,\ldots,G_r$ for some $r \ge 2$. Let $V_i = V(G_i), i=1,\ldots,r$.

Let $U=V_1$. So $\overline{U} = V-V_1$. We claim that $F$ is exactly the set of edges $E(U, \overline{U}) = \{xy \in E: x \in U, y \in \overline{U} \}$. It is clear that $F$ contains $E(U, \overline{U})$ because otherwise the removal of $F$ from $G$ will not isolate $U$ from the rest of the graph. If $F$ contains any edges in $E(G)-E(U, \overline{U})$, then these edges can be removed from $F$ to give an edge-cut $E(U, \overline{U})$ which is properly contained in $F$, contradicting the minimality of $F$. Hence, $F = E(U, \overline{U})$.

Answer 3

Hint: any edge-cut disconnects $G$ into at least two components. Show that if there are more than two components, or if any edge in the cut does not go between the two components, you can modify the edge-cut to get a smaller one (so it wasn't minimal).

Answer 4

Let's remove edges of $F$. We get two connected components $H_1$ and $H_2$. Let $U = V(H_1)$ then $\overline{U} = V(H_2)$. Obviously it is a desired set $U$.