Bridges

• Read 4.1, pages 85-87
  • When is an edge called a bridge?
  • Can an edge that reaches a leaf vertex be a bridge?
  • Identify the bridges for:
    • path graphs
    • cycle graphs
    • complete graphs
  • Can a disconnected graph have bridges?
  • Is this a valid restatement of an edge \(e\) being a bridge for a graph \(G\): “the two vertices incident to the edge are on different components of the graph \(G-e\)”
  • Prove theorem 4.1: An edge is a bridge if and only if it lies on no cycle of the graph.
  • Practice problems: 4.1, 4.2 (Exercise 2.9 can help here), 4.5a (induction on \(n\))
  • True or False: If \(H\) is a spanning subgraph of \(G\), and \(e\) is an edge in \(H\) which is a bridge in \(G\), then it is also a bridge in \(H\). What about the other way around?
  • True or False: A graph cannot have exactly one non-bridge edge.
  • Challenge problems: 4.5b, 4.6