# Edges in and out of cycles and their relation to connectivity of the graph

We know that if an edge is a part of a cycle in an undirected connected graph $G$, then if we remove that edge the graph is still connected.

Is the opposite true? If an edge is not a part of a cycle in a connected graph $G$, and we remove that edge, then the graph we get is disconnected?

P.S.: I think that it is true, and the direction for a proof is to look at one vertex it connects, and the edges that connect the vertices with it as on component, and the other end as another component, and showing that if we cut out that edge, we get two components, such that the graph is not connected. What do you think?

• Yes. If the edge is $ij$, there can't by any other path from $i$ to $j$, since that would give a cycle through the edge. So removing it, in particular, disconnects $i$ from $j$. Edges like this are called bridges. Apr 5, 2014 at 15:57
• @Louis Make an answer? Apr 5, 2014 at 16:47

Yes. Let $G$ be a graph, and suppose that the edge $ij\in E(G)$ is not on any cycle. This implies that every path $P$ from $i$ to $j$ in $G$ uses the edge $ij$, since, otherwise, $P\cup \{ij\}$ is a cycle in $G$. In particular, removing $ij$ from $G$ disconnects $i$ from $j$.