What is K-connected Graph?

A k-connected graph is a type of graph where removing k-1 vertices (and edges) from the graph does not disconnect it. 

In other words, there are at least k distinct paths between any two vertices in the graph, and the graph remains connected even if k-1 vertices or edges are removed. The parameter k is known as the connectivity of the graph. The higher the connectivity of a graph, the more robust it is against failures or attacks.

A 4-connected Graph

Properties of k-connected Graph:

• Robustness: A k-connected graph is more robust against vertex or edge failures than a graph with lower connectivity. Removing k-1 vertices or edges from a k-connected graph does not disconnect it.
• Minimum degree: In a k-connected graph, every vertex has a degree of at least k. This means that the graph is densely connected and has many paths between its vertices.
• Separability: A graph is k-connected if and only if it is not separable into two disconnected subgraphs by removing k-1 vertices.
• Augmentation: Every k-connected graph can be augmented to a (k+1)-connected graph by adding edges between any two sets of k vertices that are not already connected.
• Planarity: In a planar k-connected graph, the number of vertices is at least 2k, and the number of edges is at least 3k – 6.

How to identify a k-connected Graph?

• Brute force approach: One way to identify if a graph is k-connected is to remove all possible subsets of k-1 vertices (or edges) and check if the graph remains connected after each removal. This approach is not efficient for large graphs, but it can be used for small graphs. 
• Max-flow min-cut theorem: According to the Max-flow min-cut theorem, the maximum flow in a graph is equal to the minimum cut in the graph. Therefore, we can use a max-flow algorithm to find the minimum cut of a graph, and if the minimum cut is greater than or equal to k, then the graph is k-connected.
• Connectivity algorithm: We can use a connectivity algorithm such as Tarjan’s algorithm or Hopcroft–Karp algorithm to find all the cut-vertices and cut-edges in a graph. If there are no cut-vertices and cut-edges of size less than k-1, then the graph is k-connected.
• DFS Algorithm: First we, check if K is greater than or equal to 2 and less than the total number of vertices in the graph. If K is greater than or equal to the number of vertices in the graph minus one, then the graph cannot be K-connected. Next, for each vertex in the graph, perform a DFS traversal and count the number of vertices that are visited. If the number of visited vertices is less than K, then the graph is not K-connected.
  If the above condition is not satisfied for any vertex in the graph, then the graph is K-connected.

Sudo code for dfs algorithm

function isKConnected(Graph G, int K):
    visited = {False} * |V(G)|
    if K < 2 or K >= |V(G)|:
        return False
    for each vertex u in G:
        count = 0
        DFS(u, visited, count)
        if count < K:
            return False
    return True

function DFS(vertex v, visited, count):
    visited[v] = True
    count += 1
    for each adjacent vertex w of v:
        if not visited[w]:
            DFS(w, visited, count)

Implementation:

Graph is not K-connected.