Given a graph, a subset of the vertices is an independent set if there are no edges between the vertices in the subset. Let’s take a look at a quick example to see what this means.

We can see that there is an edge between the following points:

• Points 1 and 2
• Points 1 and 3
• Points 1 and 4
• Points 2 and 3
• Points 2 and 5
• Points 3 and 5
• Points 4 and 5
• Points 4 and 6
• Points 5 and 6

When trying to find the maximum independent set, we’ll try to find the maximum amount of points that are not connected directly. Where do we start? Usually, we’ll look for a point that is connected to two other points. In this case, the only point that meets the criteria is point 6. Point 6 is connected to points 4 and 5.

We know that since points 4 and 5 are connected to point 6, they cannot be part of the maximum independent set, and any edge connecting those points is severed.

We can see that there are three points left in the graph: points 1, 2, and 3. If we choose either of the points, the other two points will automatically not be part of the maximum independent sets. That’s fine since there can be multiple maximum independent sets. For this example, we’ll choose vertex 1. Vertices 2 and 3 will be crossed out and all edges to which they’re connected to will be severed. The maximum independent set for this example is 1,6.

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