yakin
- 42
- 0
How to find if a graph has a cut-edge/bridge and cut vertices. In other words, i am mixed up between cut edge and cut vertices? What is the difference and how one can find these in a graph?
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 reply · 2K views
Sudharaka
Gold Member
MHB
- 1,558
- 1
yakin said:
Hi yakin, :)
Cut edges are edges when deleted increases the number of connected components in the graph. That is by deleting a cut edge you will disconnect the graph into $n+k$ connected components where $n$ is the current number of connected components and $k$ is an integer which depends on the cut edge you remove. Similarly a cut vertex is a vertex when deleted increases the number of connected components in the graph. Here is a picture depicting cut edges and cut vertices. The cut edges are marked in red and the cut vertices are marked in black.
