28.1.2. Definition of a Vertex Cut

Try these first

1. 1.

   Define a vertex cut.

   Hint

   Think about the connection between vertices and how their removal affects it.

2. 2.

   What is the vertex connectivity for a complete graph?

   Hint

   Consider how many vertices you can remove without disconnecting it.

3. 3.

   What is a vertex cut?

   • A set of edges
   • A set of vertices
   • A single vertex

   Hint

   Remember what kind of elements are removed to disconnect the graph.

4. 4.

   True or False: A complete graph can have a vertex connectivity of 0.

   • True
   • False

   Hint

   Consider how a complete graph is structured.

5. 5.

   Given a graph with vertices labeled A, B, C, D, and edges (A-B, A-C, B-C, B-D), identify a vertex cut.

   Hint

   Visualize which connections break when B is removed.

6. 6.

   Explain why in any connected non-complete graph, the vertex connectivity is less than or equal to the minimum degree.

   Hint

   Reflect on the connectivity definitions.