If $A$ is a set of edges such that $S \cap T$ is non-empty, where $T$ is the edges of any spanning tree of $G$, then $S$ contains a cutset of $G$

Question

We have a connected, undirected graph $G$, and suppose we have a set of tree edges $T_1,\cdots,T_n$ of $G$ which encompass all possible spanning trees of $G$. Now suppose that we construct a set of edges $A$ such that $A \cap T_i \neq \emptyset$ for all $1 \leq i \leq n$.

$A$ is not necessarily a unique set, for an edge $e$ to qualify being a member of $A$ it must merely be part of at least one of $T_i$, so at its largest $A$ will just be a set of all edges of $G$.

How to show that this set $A$ contains a subset which is the cutset of $G$?

Answer 1

If we delete all edges in $A$ from $G$, then the resulting graph $G-A$ cannot be connected. (If $G-A$ were connected, it would have a spanning tree $T$, but then $T$ would also be a spanning tree of $G$ that has no edges in common with $A$.)

By the loose definition, that makes $A$ a cutset, so we're done.

Some people take the definition of a cutset more strictly, either as

• the set of all edges between two disjoint sets $S, T \subseteq V(G)$ with $S \cup T = V(G)$, or even
• the above, but with the additional requirement that $G[S]$ and $G[T]$ are connected.

If $G-A$ is disconnected, it is possible to prove that $A$ contains a cutset by either of the stricter definitions, too. (More precisely, if $B \subseteq A$ is a minimal subset of $A$ such that $G-B$ is not connected, then $B$ satisfies both of the stricter definitions.) So we win in any case.