Blocks

• Read section 5.2, pages 111-114
  • When do we call a graph nonseparable?
  • Prove theorem 5.7: A graph of order at least \(3\) is nonseparable if and only if every two vertices lie on a common cycle.
    • In the forward direction part of the proof, the case of \(d(u, v)=1\) is handled right-away by the fact that the graph has no bridges. Explain.
    • Explain how the inductive step for that direction works, in particular figure 5.3.
  • What do we refer to as a block in a separable graph?
  • What are the blocks in a path graph? In a cycle graph? A complete graph?
  • Looking at Figure 5.4, make sure you understand why the identified graphs are blocks.
  • Practice on exercise 5.9.
  • If a vertex is a cut-vertex of a graph, is it also a cut-vertex of any induced subgraph that contains it?
  • Prove theorem 5.8: The relation \(R\) on edges defined by \(e R f\) iff \(e=f\) or if \(e\) and \(f\) lie on the same cycle is in fact an equivalence relation. You will need to show it is reflexive, symmetric and transitive. Make sure to draw a graph of the proof of transitivity.
  • Show that the graph induced by the edges of any one of the equivalence classes is a block (i.e. you have to show that it is nonseparable, and also that it cannot be extended).
  • Prove corollary 5.9: Distinct blocks are edge-disjoint, have at most one vertex in common, and if they do have a vertex in common then it is a cut-vertex of the graph.
  • Work out exercise 5.10.
  • Practice problems: 5.12, 5.13