4.1 Vertex and edge connectivity

Connectivity in graphs measures how well-connected a structure is. It's crucial for understanding network strength and weak points. Vertex and edge connectivity tell us the minimum elements needed to disconnect a graph.

Calculating connectivity involves algorithms like Ford-Fulkerson and max-flow min-cut. The relationship between connectivity types is expressed as κ(G) ≤ λ(G) ≤ δ(G), with Whitney's theorem providing key insights into graph structure and vulnerability.

Connectivity Concepts

Vertex and edge connectivity

• Vertex connectivity (κ(G)) represents minimum vertices removed to disconnect graph measures vertex-disjoint paths between any two vertices (complete graphs κ(G) = n - 1, n = number of vertices)
• Edge connectivity (λ(G)) represents minimum edges removed to disconnect graph measures edge-disjoint paths between any two vertices (complete graphs λ(G) = n - 1, n = number of vertices)
• Connectivity relates to graph structure higher connectivity indicates robust well-connected graph lower connectivity suggests vulnerable points (bridges, cut-vertices)

Calculation of graph connectivity

• Vertex connectivity calculation employs Menger's theorem κ(G) equals minimum vertex-disjoint paths between non-adjacent vertices uses Ford-Fulkerson algorithm converting graph to flow network finding maximum flow
• Edge connectivity calculation utilizes max-flow min-cut theorem finds minimum cut in graph applies global min-cut algorithms (Karger's, Stoer-Wagner)
• Manual calculation steps
  1. Identify potential vertex or edge cuts disconnecting graph
  2. Remove vertices or edges systematically to find minimum number required
  3. Verify no smaller cut exists

Connectivity vs minimum degree

• Inequality relationship $κ(G) ≤ λ(G) ≤ δ(G)$ where κ(G) vertex connectivity λ(G) edge connectivity δ(G) minimum degree of graph
• Implications vertex connectivity always less than or equal to edge connectivity edge connectivity always less than or equal to minimum degree removing edges generally less disruptive than removing vertices
• Special cases include trees κ(G) = λ(G) = δ(G) = 1 and complete graphs κ(G) = λ(G) = δ(G) = n - 1

Whitney inequality for connectivity

• Whitney's theorem states for any graph G with at least three vertices $κ(G) ≤ λ(G) ≤ δ(G)$
• Proof outline demonstrates removing λ(G) - 1 edges cannot disconnect graph shows removing λ(G) vertices always disconnects graph concludes κ(G) ≤ λ(G)
• Key proof steps use contradiction to prove κ(G) ≤ λ(G) show removing δ(G) - 1 edges from vertex cannot isolate it conclude λ(G) ≤ δ(G)
• Significance provides bounds for connectivity measures helps estimate graph vulnerability and robustness (network reliability, fault tolerance)