Скачать или смотреть Structural Graph Theory 2021 Lecture-9

In today's lecture (15/02/2021), we discussed two important decompositions associated with a graph:

1. Block decompositions -- this is a unique decomposition associated with any graph G (each member of the decomposition corresponds to a block of G -- i.e., a maximal nonseparable subgraph of G).

2. Ear decompositions -- each nonseparable graph G (that is not K_1 or K_2) may be generated from a cycle by adding an ear at each step so that, at each stage, we have a nonseparable subgraph (the starting cycle, and ears, are members of this ear decomposition which is not unique in general) -- this may be viewed as a generation theorem/tool (i.e., an induction tool) for nonseparable graphs.