Show that the block graph of any connected graph is a tree


A. Show that the block graph of any connected graph is a tree.
Hint: Deduce the connectedness of the block graph from that of the graph itself, and its acyclicity from the maximality of each block.

B. Let e be an edge in a 2-connected graph G 6= K4. Show that either G - e or G/e is again 2-connected. Deduce a constructive characterization of the 2-connected graphs analogous to Theorem 3.2.3. and 3.2.5
Hint: Induction along Proposition 3.1.3. 

Solution Preview :

Prepared by a verified Expert
Mathematics: Show that the block graph of any connected graph is a tree
Reference No:- TGS01236746

Now Priced at $20 (50% Discount)

Recommended (94%)

Rated (4.6/5)