4.7.1. Counting Argument

Try these first

1. 1.

   Define vertex connectivity in your own words.

   Hint

   Think about how you would break apart a graph.

2. 2.

   What is edge connectivity?

   Hint

   Consider what you would cut to separate a graph into parts.

3. 3.

   What is the relationship between vertex connectivity and edge connectivity?

   • Vertex connectivity is greater than edge connectivity
   • Vertex connectivity is less than or equal to edge connectivity
   • They are equal

   Hint

   Remember, removing vertices does not add connections.

4. 4.

   True or False: Minimizing the number of edges in a graph while maintaining connectivity is possible with less than m edges.

   • True
   • False

   Hint

   Think about the definitions we've discussed.

5. 5.

   Formulate a simple graph with l=2, m=3, n=4 and describe its properties in detail.

   Hint

   Visualize how nodes connect back to maintain compactness.

6. 6.

   Consider a graph with 7 vertices and the following degrees: 3, 4, 2, 5, 6, 1, 1. Analyze its connectivity and characterize potential edge removals.

   Hint

   Use the degree counts to see if connections could be severed.