28.1.7. Relationship Between Vertex Connectivity and Edge Connectivity

Try these first

1. 1.

   Define a vertex cut.

   Hint

   Think about what happens when you remove vertices.

2. 2.

   What is edge connectivity?

   Hint

   Consider edge cuts.

3. 3.

   What does vertex connectivity measure?

   • The smallest edge cut
   • The smallest vertex cut
   • The maximum degree

   Hint

   Think about how vertices interact.

4. 4.

   True or False: In a disconnected graph, both vertex and edge connectivity are non-zero.

   • True
   • False

   Hint

   What happens when a graph is already split?

5. 5.

   Consider a graph with vertices forming a cycle. Determine both vertex and edge connectivity.

   Hint

   Think about cycles' resilience to cuts.

6. 6.

   In a complete graph of 5 vertices, what would be the vertex and edge connectivity?

   Hint

   Visualize how many key nodes remain to maintain connectivity.