Connecitivity graph. Easy task.

Question

Let $G=(V,E) $ is a connectivity graph and $e\in E$ . Prove that $G'=(V, E - \{e\} ) $ is connectivity $\iff$ e is an edge $\in$ any cycle in $G$. Please help me with that.

Answer 1

"Connected graph" (not "connectivity graph") means there's a path between every two vertices in $V$. $(V, E - \{e\})$ simply means removing the edge $e$ from the graph.

Suppose $e$ is an edge in some cycle. If you remove $e$, could $G$ stop being connected? It might happen only because some paths to connect some vertices used $e$. Can you fix those paths using what you know about $e$ to make sure all these vertices stay connected?

Suppose $e$ is not an edge in any cycle. The two vertices that are connected by $e$ - what happens to them after you remove $e$ from the graph? If $G$ is still connected they must have a path between them - is it possible given what you know about $e$?

Answer 2

The following is equivalent:

1. $e$ does not lie on any cycle of $G$,
2. $e$ is a bridge,
3. removing $e$ from $G$ increases number of connected components.

If you are still uncertain about $1 \leftrightarrow 2$, try proving it by assuming $e$ does not lie on on any cycle (if $e=uv$, assume there is a path from $u$ to $v$ in $G-uv$; by adding an edge $uv$ back again, you obtain a contradicting cycle).

Note that:

• I assume that that connectivity graph = connected graph.
• I do not have enough rep to write this in comment.