4.1.4. Tutorial 9: Part I

Try these first

1. 1.

   Define vertex connectivity.

   Hint

   Think about the vertices that connect different parts of a graph.

2. 2.

   What is the edge connectivity of a graph?

   Hint

   Consider the edges that maintain the graph's continuity.

3. 3.

   What is the minimum degree in a graph?

   • The highest degree of a vertex
   • The smallest degree of all vertices
   • The average degree of all vertices

   Hint

   Think about which vertex has the least connections.

4. 4.

   True or False: Vertex connectivity is always greater than or equal to edge connectivity.

   • True
   • False

   Hint

   Consider how removing vertices affects edge connections.

5. 5.

   Prove or disprove that among any three graphs, the union's vertex connectivity is less than or equal to the smallest vertex connectivity among the three. Provide an example.

   Hint

   Think about what happens to the graph structure when combining different graphs.

6. 6.

   Select a random simple graph and construct its Cartesian product with another random graph. Analyze the resulting graph's properties.

   Hint

   Remember the rules for connecting vertices based on original adjacency.