1.8. Graph Connectivity

Try these first

1. 1.

   Define a subgraph.

   Hint

   Think about what a smaller graph could include.

2. 2.

   What is a cut vertex?

   Hint

   Consider what happens if you remove important connectors in a network.

3. 3.

   What is a proper subgraph?

   • A graph identical to the original
   • A smaller graph with fewer vertices/edges
   • A disconnected graph

   Hint

   Consider what distinguishes it from the original graph.

4. 4.

   T/F: A cut vertex increases graph connectivity when removed.

   • True
   • False

   Hint

   Visualize what happens to the graph structure.

5. 5.

   Given a graph with vertices A, B, C, D connected by edges {AB, AC, CD}, identify and justify any cut vertices.

   Hint

   Consider how removing each vertex impacts total connections.

6. 6.

   Create and analyze a graph demonstrating both cut edges and cut vertices; explain your findings.

   Hint

   Draw it out to visualize how components are affected.