In this lesson, we will be studying graph cliques and independent sets. Let me start with the following problem. I give you a friendship graph where each vertex corresponds to a person, and there is an edge between two people if they're friends. And I ask you to find the largest clique in this graph. And the clique is a set of people which all know each other. It's quite easy to find a clique of size three in this graph. Three people which know each other. Is there a larger clique in this graph? First of all, if I want to find the larger clique, then we can ignore vertices of the degree less than three. Indeed, if we only want to find a clique of size four or five, or even larger, then every vertex in this clique must have a degree of at least three. So we can safely remove vertices of degree zero, one, and two. Now we have only five vertices. Can we have a clique size five? No, because there are two people which don't know each other. The blue one doesn't know the green one. So the largest clique in this graph is of size three or four. Let's try to find the clique size four. Between blue and green one, we have to choose at most one. Let's say I want to take the green one. And then I can take these three people which altogether form clique of size four. So the largest clique in this graph is size four. Now, I know that the largest clique in this graph is of size four. And I'm asking, what's the largest set of strangers in this graph? What's the largest set of people such that no two of them know each other? First of all, I can only take at most one person from the clique. Because if I take two of them, they will know each other. This is a clique. Okay, so I can only take at most one of them from the clique. But how many can I take out of the clique? Can I take all four of them? No, because the blue one and the orange one know each other. So, I can only take at most three people out of the clique, and at most one from the clique. So the largest set of strangers is of size at most four. Can I find the set of strangers of size four? Yes, I can. I can take these three people out of the clique. They don't know each other. And I can also add this person from the clique. These 4 people are strangers. So this is the largest group of strangers in the given graph. Here is another interesting problem. Recall that the complement of a graph is a graph which contains an edge if and only if the original graph doesn't contain this edge. For example, the complement of this empty graph is a full graph. I asked you to construct a graph that shows that its complement, there are four vertices without any edges between them. It's easy to construct one of these graphs. We just draw all edges between some four vertices of the original graph. Then, by the definition of the complement graph, there are no edges between these four vertices in its complement. And you can add more edges in the original graph. It doesn't change the fact you have four vertices with all edges in between them. So in that complement, you have four vertices without edges between them.