0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.