Lesson 1

Problem. Below is a group of eight people. People who know each other are connected by an edge. Find the size of the largest subgroup in which everyone knows each other. And conversely: find the size of the largest subgroup in which no two people know each other. Formally, find the maximum clique size and the maximum independent set size. Try it!