Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
3  
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. –  Louis Apr 5 at 15:57
1  
@Louis Make an answer? –  Yuval Filmus Apr 5 at 16:47

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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. –  Pål GD Apr 6 at 21:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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