4.4. Question 3

Try these first

1. 1.

   What is vertex connectivity?

   Hint

   Think about how many vertices you need to remove to make a graph fail.

2. 2.

   Define edge connectivity.

   Hint

   Consider the edges that connect the different parts of the graph.

3. 3.

   What is the definition of vertex connectivity?

   • A) Minimum edges to disconnect a graph
   • B) Minimum vertices to disconnect a graph
   • C) Total number of edges in a graph
   • D) Degree of the highest vertex

   Hint

   Think about how many roads (vertices) you'd need to block to stop traffic.

4. 4.

   Is it true that graph connectivity is higher in complete graphs than in non-complete ones?

   • True
   • False

   Hint

   Consider what makes a complete graph complete.

5. 5.

   Design a non-complete graph with at least 6 nodes and identify its vertex and edge connectivity metrics.

   Hint

   Visualize how many paths lead to disconnecting the graph.

6. 6.

   Prove that in a non-complete graph, at least one of the connectivity metrics must be less than the total number of nodes.

   Hint

   Think about how the total connection must yield a less-than-n metric.