[Math] Cut property for minimal spanning trees.

discrete mathematicsgraph theory

The question is presented as follows:

Prove the following cut property. Suppose all edges in $X$ are part of a minimum spanning tree of a graph $G$. Let $U$ be any set of vertices such that $X$ does not cross between $U$ and $V(G)-U$. Let $e$ be an edge with the smallest weight among those that cross $U$ and $V-U$. Then $X\cup \{e\}$ is part of some minimum spanning tree.

The statement of the problem confuses me. I am not sure what "Let $U$ be any set of vertices such that $X$ does not cross between $U$ and $V(G)-U$" means. Could someone explain what the idea is here?

Best Answer

An edge $e$ crossing $U$ and $V-U$ means that one endpoint of $e$ is in $U$ and another is in $V-U$.

For your statement, we can first let $T$ be a minimum spanning tree containing $X$. As stated, let $e$ be an edge with the smallest weight among those that cross $U$ and $V-U$.

If $e\in T$, then the statement holds trivially.

If $e\notin T$, then consider $T+e$, which contains exactly one cycle $C$, and $C$ crosses $U$ more than once. Therefore, we can have $e'\neq e$ in $C$ with $e'$ crossing $U$. Note that $T'=T-e'+e$ is also a spanning tree, as $T'$ is spanning and connected. Also, $T'$ is a minimum weight spanning tree, since weight of $e$ is not greater than that of $e'$. Hence the statement holds.