28.1.6. Upper Bounds on Vertex Connectivity and Edge Connectivity

Try these first

1. 1.

   What is a vertex cut in a graph?

   Hint

   Think of how removing certain points affects connections.

2. 2.

   What is the range of vertex connectivity for any graph?

   Hint

   Connectivity relates to the ability to disconnect the graph.

3. 3.

   What is the vertex connectivity of a complete graph?

   • 0
   • 1
   • n-1

   Hint

   Think about how many points you can remove while still keeping the graph connected.

4. 4.

   True or False: Every disconnected graph has a vertex connectivity of 0.

   • True
   • False

   Hint

   Consider the definition: Is it already disconnected?

5. 5.

   Design a specific graph with 5 vertices and determine both its vertex and edge connectivity. Detail your process.

   Hint

   Consider simple configurations first.

6. 6.

   Give a real-world analogy for vertex and edge connectivity along with a scenario illustrating their importance.

   Hint

   Think about how cities rely on roads and intersections.