Connectivity

• a path connects two vertices
• an undirected graph is called connected if every pair of distinct vertices in the Graph is connected; otherwise, it is called disconnected.
• an undirected graph is called k-vertex-connected or k-edge-connected if no set of k-1 vertices, respectively edges, exists that, when removed, disconnects the Graph
• a k-vertex-connected Graph is often called k-connected.
• a directed graph is called weakly connected if the corresponding undirected graph is connected.
• it is strongly connected or strong if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u, v.