1
$\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$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
-2
$\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)$.

| cite | improve this answer | |
$\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.