4.3.2. Edge Set Cardinality

Try these first

1. 1.

   What is vertex connectivity?

   Hint

   Think about how many vertices you need to take away.

2. 2.

   Define edge connectivity.

   Hint

   Consider the edges connecting the vertices.

3. 3.

   What is the relationship between vertex connectivity, edge connectivity, and minimum degree?

   • Vertex ≤ Edge ≤ Minimum Degree
   • Edge ≤ Vertex ≤ Minimum Degree
   • Minimum Degree ≤ Vertex ≤ Edge

   Hint

   Think about how removing elements affects connectedness.

4. 4.

   True or False: Edge connectivity is always greater than vertex connectivity.

   • True
   • False

   Hint

   Recall the definitions of both terms.

5. 5.

   Given a graph with a total vertex count of 10 and a missing edge set resulting from removing vertices, derive the edge set cardinality.

   Hint

   Use the relationships of vertex degrees before and after deletion.

6. 6.

   Create a graph where vertex connectivity equals edge connectivity but is less than minimum degree, and explain your reasoning.

   Hint

   Ensure your selections lead to edges and vertices that satisfy all three conditions.