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?

$\endgroup$
  • 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 Apr 5 '14 at 15:57
  • 1
    $\begingroup$ @Louis Make an answer? $\endgroup$ – Yuval Filmus Apr 5 '14 at 16:47
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.

$\endgroup$
  • $\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$ – Pål GD Apr 6 '14 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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