Lesson 1

Problem. You are organizing a party for a small company. You want to invite as many people as possible, but you also want each participant to feel as relaxed as possible. To achieve this, no attendee should have their direct manager present.

The tree in the figure shows the manager-subordinate relationships in the company. What is the maximum number of employees that can be invited to the party? (More formally: what is the size of the maximum independent set in this tree?)