Graph in Problem 1.

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-V, B) is biconnected, where VB is the subset of vertices incident to (touched by) edges in B. (L.e., GB is B's edge- induced subgraph. Maximal means you can't 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 don't need to give, but basically it's 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 component's 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 weren't 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: A, D.LA, ED, ,D,I,E,J,I,J) Component 2: B, E Component 3: HC,H,C,,HI Component 4: F, G), [F, J), {G, K), {J, K, and Component 5:K, L)) Find and list the biconnected components of the graph in