1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Louis
    Commented Apr 5, 2014 at 15:57
  • 1
    $\begingroup$ @Louis Make an answer? $\endgroup$
    – Yuval Filmus
    Commented Apr 5, 2014 at 16:47

1 Answer 1

Reset to default
5
$\begingroup$

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$.

These kinds of edges are called bridges.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice answer. Wanted to add that vertices that disconnects the graph when you remove them are called cut vertices or articulation points. See, e.g., biconnected component. $\endgroup$
    – John Kemeny
    Commented Apr 6, 2014 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.