1. Engineering
  2. Computer Science
  3. prove the following statement 1 in fact every edge is...

Question: prove the following statement 1 in fact every edge is...

Question details

2. [10 points] A connected graph is biconnected if it has no articulation points. A biconnected component of an undirected graph G (V, E) is a maximal subset B of the edges with the property that the graph GB (VB, B) is biconnected, where VB is the subset of vertices incident to (touched by) edges in B. (Le., GB is Bs edge- induced subgraph. Maximal means you cant enlarge B without destroying its biconnected property.) Note that a graph consisting of single edge is biconnected. Consequently, every edge in G is part of some biconnected component. In fact, every edge is part of exactly one biconnected components. (This really needs a proof, which you dont need to give, but basically its true because if some edge were in two components, their union would also be biconnected, contradicting the maximality condition.) So, the biconnected components partition the edges. To reiterate a point that many people overlook on first reading: a biconnected component is a set of edges, not a set if vertices. Each components edge-induced subgraph of course defines a set of vertices, but these vertex sets do not partition the vertices: they overlap. (Where?) Another fact, just to help your intuition: two distinct edges lie on a common simple cycle if and only if they are in the same biconnected component. (This motivates the term biconnected-there are always two independent paths between places. Again, these statements need careful proof, but the idea is simple: if there werent two paths, you could disconnect the graph by removing some vertex on the one path.) For example, the biconnected components of the graph below are the five sets of edges:

. Component 1: {{A, D), {A, E}, {D, E}, {D, 1}, {E, J), {I, J)) Component 2: (B, E Component 3: C, H), C,I,HI . Component 4: {{F, G), {F, Λ, {G, 자, {J, K}}, and Component 5: JK,L

Prove the following statement:

1) In fact, every edge is part of exactly one biconnected components.

2) Another fact, just to help your intuition: two distinct edges lie on a common simple cycle if and only if they are in the same biconnected component.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution