4.6.1. Vertex Chromatic Number

Try these first

1. 1.

   What is the vertex connectivity of a complete graph with 4 vertices?

   Hint

   How many vertices do you need to remove to disconnect the graph?

2. 2.

   Define edge connectivity.

   Hint

   Think about how many edges you would need to cut.

3. 3.

   What is vertex connectivity?

   • Number of edges to disconnect a graph
   • Number of vertices to disconnect a graph
   • Minimum degree of a vertex

   Hint

   Consider how we define connectivity.

4. 4.

   True or False: Edge connectivity can be less than vertex connectivity.

   • True
   • False

   Hint

   Review the definitions carefully.

5. 5.

   Construct a non-complete graph with vertex connectivity 2, edge connectivity 2, and a minimum degree of 2. Explain your reasoning.

   Hint

   Ensure connectivity conditions are met while keeping it non-complete.

6. 6.

   Prove that for any simple graph with n vertices, the maximum degree is at least n-1.

   Hint

   Use a connectivity argument to support degree calculations.