We know that if an edge is a part of a cycle in an undirected connected graph G,

Question

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?

Explanation / Answer

Yes. Let G be a graph, and suppose that the edge ij?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?{ij} is a cycle in G. In particular, removing ij from G disconnects i from j.

These kinds of edges are called bridges.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.