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. 
 A: Let $T$ be any spanning tree of a graph $G$ and $E$ an edge-cut. We need to show that $E\cap E(T)$ is non empty (then $T$ contains at least one edge of that arbitrary edge-cut). Let $v$ and $w$ be two vertices in different components of $G\setminus E$ (that is $G$ with edges $E$ removed). Since $T$ is a spanning tree, there is a path $P$ from $v$ to $w$ in $T$. If we had $E\cap E(T)=\emptyset$, then $T$ would be a subgraph of $G\setminus E$ and therefore $P$ would also connect $v$ and $w$ in $G\setminus E$, contradiction to the choice of $v$ and $w$. Hence $E\cap E(T)$ is non empty.
A: 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)$. 
