28.1.1. Vertex and Edge Connectivity

Try these first

1. 1.

   Define vertex connectivity.

   Hint

   What does κ(G) represent?

2. 2.

   What is a vertex cut?

   Hint

   Think about how many vertices you need to remove.

3. 3.

   What is a vertex cut?

   • A single vertex
   • A group of edges
   • A subset of vertices

   Hint

   Think about what needs to be removed to disconnect.

4. 4.

   True or False: The edge connectivity of a disconnected graph is 1.

   • True
   • False

   Hint

   Consider what happens in a graph that is already disconnected.

5. 5.

   Consider a graph with vertices {A, B, C, D, E} and edges {AB, AC, AD, BE, CE}. Determine whether the following sets are vertex cuts: {B}, {A, C}. Explain your reasoning.

   Hint

   Analyze how the removal affects the connectivity of other vertices.

6. 6.

   In a connected, non-complete graph with 5 vertices, prove that if the minimum degree is 2, then κ(G) ≤ 2. Provide an example graph to illustrate your answer.

   Hint

   Consider the structure and degree of vertices.