Clique Detection

Determine whether a given set of vertices forms a clique in an undirected graph.

graphs cliques adjacency-matrix sets

An undirected graph is represented by an adjacency matrix `adj` where `adj[i][j]` is `True` if there is an edge between vertex `i` and vertex `j`, and `False` otherwise. The graph has no self-loops (i.e., `adj[i][i]` is always `False`).

Write a function `is_clique(adj, vertices)` that returns `True` if the given list of vertices forms a clique, and `False` otherwise. A clique is a subset of vertices such that every pair of distinct vertices in the subset is directly connected by an edge.

The function should handle the edge case where the `vertices` list is empty or contains only one vertex (both are considered a clique). It should also handle cases where `vertices` may contain duplicate entries (duplicates should not affect the result).

Constraints

1 <= len(adj) <= 20
`adj` is a square matrix of booleans with `len(adj) == len(adj[0])`.
`adj[i][i]` is always `False`.
`adj` is symmetric: `adj[i][j] == adj[j][i]`.
0 <= vertices[i] < len(adj) for all i.
The `vertices` list may contain duplicates.
Time complexity: O(k^2) where k = len(vertices).

Example

>>> adj = [
...     [False, True, False],
...     [True, False, True],
...     [False, True, False]
... ]
>>> is_clique(adj, [0, 1])
True
>>> is_clique(adj, [0, 1, 2])
False
>>> is_clique(adj, [])
True
>>> is_clique(adj, [1])
True

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a set of unique vertices to avoid checking duplicates twice.

For each unordered pair (i, j) of distinct vertices in the set, check if adj[i][j] is True.

If all pairs are connected, return True; otherwise return False early.

Remember that the graph is undirected, so adj[i][j] equals adj[j][i], but you can just check one direction.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.