4.2.1. Introduction to Graph Construction

Try these first

1. 1.

   Define vertex connectivity in your own words.

   Hint

   Think about what happens if you remove vertices.

2. 2.

   What does edge connectivity represent?

   Hint

   Consider the edges that connecting vertices.

3. 3.

   What is the minimum number of vertices that must be removed to disconnect a graph called?

   • Vertex Connectivity
   • Edge Connectivity
   • Minimum Degree

   Hint

   Focus on vertex removals.

4. 4.

   True or False: Edge connectivity is always greater than minimum degree.

   • True
   • False

   Hint

   Think of a sparse versus a dense graph.

5. 5.

   Design a graph with given parameters: vertex connectivity 4, edge connectivity 3, and minimum degree 5. Provide a detailed construction process.

   Hint

   Identify the initial complete graphs and think about how many edges you need to add.

6. 6.

   Prove that a graph with vertex connectivity k must have a minimum degree of at least k.

   Hint

   Use examples with varying connections to illustrate.