CODEWITHSUNDEEP
algorithmgraphshortest-pathdijkstra
Abdul Rehman
Abdul Rehman

Reputation: 131

under what conditions graph will remain connected after removing some edge?

A graph is connected when there is a path between every pair of vertices. suppose we have an undirected graph, under what conditions graph will remain connected after removing some edge between u and v?

Upvotes: 1

Views: 57

Answers (1)

ruakh
ruakh

Reputation: 183504

There's actually not much to say — that condition is trivially equivalent to any of the following:

  • Between every pair of vertices, there's a path that does not include the edge uv.
  • There is a path from u to v that does not include the edge uv.
  • There is a cycle that includes the edge uv.

. . . but there's not really anything deeper than that.

Upvotes: 2

Related Questions