# Prove that a spanning tree of a connected multigraph contains at least one edge of every edge-cut

Problem:

Prove that a spanning tree of a connected multigraph contains at least one edge of every edge-cut, where an edge-cut is defined as the set of edges whose removal disconnects the graph.

Any hints/suggestions regarding this problem will be much appreciated.

## 1 Answer

I think the definition of edge-cut you are using may not be quite correct. A cut of $G=(V,E)$ is defined to be a pair $(A,B)$ where $A,B\subset V$, $A\cup B=V$, and $A\cap B=\emptyset$ - in other words, we partition the vertex set $V$ into to sets $A$ and $B$. Now, based on this definition of cut, I would think that what is meant by edge-cut in this context is the set of edges that go between $A$ and $B$, explicitly $\{(v,w)\in E:v\in A, w\in B\}$. From these definitions, you should think about whether it is possible for a spanning subgraph to be connected if it misses any edges between $A$ and $B$ for any cut $(A,B)$.