4.3.1. Unknown Graph G

Try these first

1. 1.

   Define vertex connectivity in your own words.

   Hint

   Think of how many people would need to leave a party to separate the remaining guests.

2. 2.

   What is the minimum degree of a graph?

   Hint

   Look for the least connected person in a group photo.

3. 3.

   What is the relationship between vertex connectivity and edge connectivity?

   • Vertex connectivity > Edge connectivity
   • Edge connectivity > Vertex connectivity
   • They are equal

   Hint

   Remember the definitions!

4. 4.

   True or False: A complete graph's vertex connectivity is 1.

   • True
   • False

   Hint

   Consider the definition of a complete graph.

5. 5.

   Construct a graph with 6 vertices that has a vertex connectivity of 3, edge connectivity of 4, and a minimum degree of 5. Justify your construction.

   Hint

   Use trial-and-error and keep connectivity rules in mind.

6. 6.

   Given a graph with 8 vertices and minimum degree of 3, show that it has at least 12 edges, and explain your reasoning.

   Hint

   Employ properties like Handshaking Lemma.