28.1.5. Edge Connectivity of a Graph

Try these first

1. 1.

   What is a vertex cut?

   Hint

   Think about what happens to a graph when specific vertices are removed.

2. 2.

   Define edge connectivity.

   Hint

   Consider how edges relate to the overall structure of a graph.

3. 3.

   What is a vertex cut?

   • A single vertex removal
   • A subset that disconnects the graph
   • An edge cut

   Hint

   Recall what disconnection means in the context of graph theory.

4. 4.

   True or False: Vertex connectivity is always less than edge connectivity.

   • True
   • False

   Hint

   Consider the definitions of both types of connectivity.

5. 5.

   You have a graph G with 5 vertices forming a pentagon. Identify the vertex connectivity and explain your reasoning.

   Hint

   Consider how cycles behave when vertices are removed.

6. 6.

   In a graph with 6 vertices where vertex degree 3 occurs, analyze its edge connectivity. What can you deduce?

   Hint

   Take into account the minimum degree per vertex.