$G$ is a connected graph, $e_1,e_2\in E\Rightarrow \{e_1,e_2\}$ form a disconnecting set

39 Views Asked by At

Assume $G$ is a connected graph and $e_1$ and $e_2$ are its edges such that every spanning tree of $G$ contains at least one of them.

Prove that $\{e_1, e_2\}$ form a disconnecting set for $G$.

I have started by drawing a graph $G$ and I have seen that every spanning tree of $G$ does contain at least one of the edges however I am unable to write a proper proof for this.

I also know that if $G$ is a connected graph an edge of $G$ that appears in every spanning tree is called a bridge and an edge of $G$ that appears in no spanning tree is a loop.

Any help would be accepted.

1

There are 1 best solutions below

2
On BEST ANSWER

If $G$ with removed edges $e_1$ and $e_2$ is connected then it has a spanning tree, which is a spanning tree for $G$ which don’t contain $e_1$ and $e_2$.