Skip to main content
2 of 2
added 13 characters in body
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

Identifying the edges that are essential for biconnectivity

Question:

If $G(V,E)$ is a biconnected symmetric graph, is it possible to identify the edges, whose deletion destroys biconnectivity, in the following way:

  • determine the union $B:= ST\cup F_1$ of a spanning tree and a maximal forest, that is edge-disjoint with $ST$
  • determine a second maximal forest $F_2$ that has no edges in common with $B$.
  • take as the critical edges those edges of $B$, that are adjacent to a vertex of degree 2 or connect different trees of $F_2$.
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76