Cut Vertices

• Read section 5.1, pages 107-110
  • What vertices do we call cut-vertices of a graph?
  • Which vertices are cut-vertices in path, cycle and complete graphs?
  • Which vertices are cut-vertices in a tree?
  • Are the vertices incident to a bridge necessarily cut-vertices?
  • Are the edges incident to a cut vertex necessarily bridges?
  • What is the smallest graph you can make with a cut-vertex?
  • Prove theorem 5.1: A vertex that is incident to a bridge is a cut-vertex if and only if its degrees is at least 2.
  • Prove corollary 5.2: A connected graph of order at least 3 with a bridge must also have a cut-vertex.
  • Prove theorem 5.3: \(v\) is a cut-vertex and we consider two vertices on different components of \(G-v\), then every path in \(G\) joining those vertices must pass through \(v\).
  • Prove corollary 5.4: A vertex is a cut-vertex if and only if there are two vertices distinct from it so that every path joining them passes through it.
  • Prove theorem 5.5: If we consider a vertex of a graph \(G\), then the vertex that is the farthest from it is not a cut-vertex.
  • Prove corollary 5.6: Every nontrivial connected graph contains at least two vertices that are not cut-vertices.
  • Work out problems 5.1, 5.2
  • Practice problems: 5.3, 5.4, 5.5, 5.6