4.8. Conclusion

Try these first

1. 1.

   Define vertex connectivity in your own words.

   Hint

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

2. 2.

   What does edge connectivity measure?

   Hint

   Consider how edges might hold a graph together.

3. 3.

   What is vertex connectivity?

   • A. The minimum number of edges to remove
   • B. The minimum number of vertices to remove
   • C. The minimum degree of the vertices

   Hint

   Think about which components are crucial for connectivity.

4. 4.

   True or False: Edge connectivity is always less than or equal to vertex connectivity.

   • True
   • False

   Hint

   Consider the definitions of both types of connectivity.

5. 5.

   Construct a simple graph with a vertex connectivity of 3, where the edge connectivity is 2, and minimum degree equals 4. Explain your reasoning.

   Hint

   Consider starting with larger graphs and trimming down.

6. 6.

   Given a connected graph with 5 vertices and 4 edges, show if it's possible to have a vertex connectivity of 2 while maintaining a high edge connectivity.

   Hint

   Map out the vertices and edges to visualize connections.