Graph Connectivity (edge-connectivity - node connectivity)

Connectivity Types

• edge-connectivity (between 2 nodes): λ(x,y) - minimum number of edges that need to be deleted to disconnect nodes x and y
  • λ(x,y) - is the size of the minimum cut between x and y
• edge-connectivity (of graph): λ(G) - minimum number of edges that need to be deleted to disconnect G
  • λ(G) = min_x≠y λ(x,y)
  • λ(G) - is the size of a minimum cut
• node-connectivity (of graph): κ(G) - minimum number of nodes/vertices that need to be deleted, such that the remaining graph is disconnected or has no edges at all
  • κ(G) - is size of minimum vertex-cut or node-cut

Naming Conventions

• a graph that has λ(G) = k, is k-connected
• a graph that has k(G) = k, is k-node-connected

Connectivity Theorems

• Harary’s Theorem
• Menger’s Theorem
• Whitney’s Theorem