Remove a vertex and all connected edges from a graph

Problem

Given a graph represented by an adjacency list and a vertex, write a program to remove the given vertex and all edges connected to that vertex.

Input Format:

• The graph is represented as an adjacency list: a dictionary or list where adj[i] contains all nodes adjacent to node i.
• For example, adj = {0: [1,2], 1: [0,2], 2: [0,1,3], 3: [2]} or adj = [[1,2],[0,2],[0,1,3],[2]] represents a graph with 4 nodes (0 to 3), where node 0 is connected to nodes 1 and 2, node 1 to 0 and 2, etc.
• The vertex to remove is given as an integer vertex (0-based index).

Examples

Example 1

graph LR
	subgraph I["Input"]
        A(0) --- B(1)
        A --- C(2):::red
        B --- C
        C --- D(3)
    end

	subgraph O["Output"]
        A2(0) --- B2(1)
        D2(3)
    end    
    
I ~~~ O    
classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff;

Input:
adj = {
        0: [1, 2],
        1: [0, 2],
        2: [0, 1, 3],
        3: [2]
}
vertex = 2

Output:
{
        0: [1],
        1: [0],
        3: []
}

Explanation: Vertex 2 and all its edges are removed from the graph.

Solution

Method 1 – Using Adjacency List

Intuition

To remove a vertex and all its edges, delete the vertex from the adjacency list and remove it from the neighbor lists of all other vertices.

Approach

1. For each vertex in the graph, remove the target vertex from its adjacency list (if present).
2. Delete the target vertex from the graph's adjacency list.
3. The resulting adjacency list represents the updated graph.

Code

C++

class Solution {
public:
        void removeVertex(std::unordered_map<int, std::vector<int>>& adj, int v) {
                for (auto& [u, nbrs] : adj) {
                        nbrs.erase(std::remove(nbrs.begin(), nbrs.end(), v), nbrs.end());
                }
                adj.erase(v);
        }
};

Java

class Solution {
        public void removeVertex(Map<Integer, List<Integer>> adj, int v) {
                for (List<Integer> nbrs : adj.values()) {
                        nbrs.removeIf(x -> x == v);
                }
                adj.remove(v);
        }
}

Python

class Solution:
        def remove_vertex(self, adj: dict[int, list[int]], v: int) -> None:
                for nbrs in adj.values():
                        if v in nbrs:
                                nbrs[:] = [x for x in nbrs if x != v]
                adj.pop(v, None)

Complexity

• ⏰ Time complexity: O(N + M), where N is the number of vertices and M is the number of edges, since each adjacency list is traversed once.
• 🧺 Space complexity: O(1), in-place modification of the adjacency list.