Let $G=(V,E)$ be a connected undirected graph and let $F\subseteq E$. Show:
G-F is disconnected $\Leftrightarrow$ for each spanning tree $T=(V,E_T)$ of $G$ we have $F\cap E_T\neq \emptyset$.
I started with $\Rightarrow$:
$G-F$ splits the graph into two connected components $A$ and $B$. Suppose $F\cap E_T=\emptyset$. A spanning tree $T$ connects all vertices of the graph. So if $F\cap E_t=\emptyset$ there cannot be a connection between $A$ and $B$. So $T$ is not a spanning tree.
Is my proof correct? I don't know how to show the other implication, thanks for help
G-F is disconnected $\Leftrightarrow$ for each spanning tree $T=(V,E_T)$ of $G$ we have $F\cap E_T\neq \emptyset$.
graph theorytrees
Best Answer
The more direct argument works by applying the principle "A graph $H$ is connected if and only if it has a spanning tree" to the graph $G-F$. (Think where we might get spanning trees of $G-F$ from, if what we have are spanning trees of $G$.) This can be used to show both directions.
Your argument for $\implies$ is also sound, but if you are a beginner in graph theory I encourage you to spell things out more. Avoid saying that two vertices in a graph are "connected" to each other; this does not have a single clear meaning, and you are using it twice in different senses. In fact:
The missing bit is that if there's no edge between $A$ and $B$, then there cannot be a path that begins in $A$ and ends in $B$, either. Eventually, this argument becomes so routine that it does not need to be spelled out, but you should be able to do so.
(Also, a minor quibble: $G-F$ does not necessarily have just two connected components $A$ and $B$, it could be more. But your argument works just fine if, for example, we let $A$ be one connected component and let $B$ be what's left over, connected or not.)