$G-F$ disconnected iff $F\cap E(T)\neq \emptyset$

42 Views Asked by At

Let $G=(V,E)$ be a undirected connected graph and $F\subseteq E$. Show that $G-F$ is disconnected iff for every spanning tree $T=(V,E(T))$ of $G$ we have $F\cap E(T)\neq\emptyset$. I thought about using the fact that a graph is connected if one only if there is a spanning tree, but I didn't get any further with that.

1

There are 1 best solutions below

0
On

If $F \cap E(T) \ne \varnothing$ for every spanning tree $T$, then the graph $G - F$ is disconnected, because it doesn't contain any spanning tree. If $G - F$ is disconnected, then for any spanning tree $T$ of the graph $G$ we have $F \cap E(T) \ne \varnothing$, because otherwise $G - F$ would have a spanning tree.