# 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.

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.
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)$.