28.1.8. Conclusion

Try these first

1. 1.

   Define vertex cut in your own words.

   Hint

   Think about what happens when you take away certain vertices.

2. 2.

   What does edge connectivity refer to?

   Hint

   Consider why you might want to remove edges.

3. 3.

   What is a vertex cut?

   • A collection of edges
   • A collection of vertices
   • A subgraph

   Hint

   Think about what parts of a graph can be removed to cause disconnectivity.

4. 4.

   Edge connectivity is represented by which symbol?

   Hint

   Consider symbols commonly used in mathematics.

5. 5.

   Given a connected graph with 7 vertices, where vertex A is connected to B, C, D, and E, while B connects back to A, C, and F, and C further connects to G. Find and justify the vertex cut(s).

   Hint

   Check how connections work before and after removal.

6. 6.

   For any arbitrary connected graph, prove or disprove that at least one vertex cut exists. Provide reasoning.

   Hint

   Think about the structure of the graph.