28.1.3. Vertex Connectivity of a Graph

Try these first

1. 1.

   Define what a vertex cut is.

   Hint

   Think about what happens if you remove certain vertices.

2. 2.

   What is vertex connectivity denoted as?

   Hint

   Remember the notation used in graph theory.

3. 3.

   What is the vertex connectivity of a complete graph with n vertices?

   • n
   • n-1
   • 0

   Hint

   Think about how many vertices you can keep connected.

4. 4.

   True or False: A vertex cut can consist of a single vertex.

   • True
   • False

   Hint

   Recall what an articulation point is.

5. 5.

   Let G be a graph with 6 vertices, where each vertex has a degree of 3. If one vertex is an articulation point, describe the implications for vertex connectivity.

   Hint

   Focus on the definition and role of articulation points.

6. 6.

   In a connected graph with 10 vertices and a minimum degree of 4, what can you say about its vertex connectivity? Discuss any exceptions.

   Hint

   Recall the upper bounds established and consider the complete graph case.