Maximum clique is a technique used to find the largest vertex cluster where each vertex is connected to each other. Let’s look at an example. We’ll examine each vertex and see what the greatest cluster of the following graph will be.

Let’s look at the first vertex. Vertex 1 is connected to vertices 2, 4, and 6. We need to make sure that each of those vertices has a connection to one another as well.

• Is vertex 2 connected to vertex 4? Yes
• Is vertex 2 connected to vertex 6? Yes
• Is vertex 4 connected to vertex 6? Yes

It looks like all of the vertices are connected to each other, so the current maximum clique that we’re observing is composed of 4 vertices: 1, 2, 4, and 6.

Let’s examine vertex 2. Vertex 2 is connected to vertices 1, 4, 3, and 5. We need to make sure that each of those vertices has a connection to one another as well.

• Is vertex 1 connected to vertex 3? No

There’s no point in continuing. It looks like we cannot use that vertex as the center-point of the max-clique creation. To have vertex 2 be the center-point of a maximum clique, all the vertices would need to be connected as is illustrated below.

Let’s examine vertex 3. Vertex 3 is connected to vertices 2 and 8.

• Is vertex 2 connected to vertex 8? No

To be part of a clique, the edge connecting vertex 2 to 8 would need to exist.

Let’s examine vertex 4. Vertex 4 is connected to vertices 1, 2, 4, 5, and 6. We need to make sure that each of those vertices has a connection to one another as well.

• Is vertex 1 connected to vertex 2? Yes
• Is vertex 1 connected to vertex 5? No

We cannot use vertex 4 as the center-point of the max-clique creation. To create a clique, vertex 1 must have an edge to vertex 5.

Let’s examine vertex 5. Vertex 5 is connected to vertices 2, 4, 6, 7, and 8. We need to make sure that each of those vertices has a connection to one another as well.

• Is vertex 4 connected to 6? Yes
• Is vertex 4 connected to 7? No

We cannot use vertex 5 as the center-point of the max-clique creation. To create a clique, all the vertices would need to be connected as is illustrated below.

Let’s examine vertex 6. Vertex 6 is connected to vertices 1, 2, 4, 5, and 7. We need to make sure that each of those vertices has a connection to one another as well.

• Is vertex 1 connected to 2? Yes
• Is vertex 1 connected to 4? Yes
• Is vertex 1 connected to 5? No

We cannot use vertex 6 as the center-point of the max-clique creation. To create a clique, all the vertices would need to be connected as is illustrated below.

Let’s examine vertex 7. Vertex 7 is connected to vertices 5 and 6. We need to make sure that each of those vertices has a connection to one another as well.

• Is vertex 5 connected to 6? Yes

Vertices 5, 6, and 7 do form a clique, however, we already found a larger clique than this one, so this is not a maximum-clique.

Let’s examine vertex 8. Vertex 8 is connected to vertices 3 and 5. We need to make sure that each of those vertices has a connection to one another as well.

• Is vertex 3 connected to 5? No

We cannot use vertex 8 as the center-point of the max-clique creation. To create a clique, vertex 3 would need to be connected to vertex 5.

We have completed looking at each of the vertices. The maximum clique that we were able to find was the one consisting of vertices 1, 2, 4, and 6.

If you liked what you read, check out my book, An Illustrative Introduction to Algorithms.