Lesson 1

Problem. You have a small local computer network that you want to protect from viruses. We assume that the connection between two computers is protected if at least one of these computers has antivirus software installed. What is the minimum number of antivirus installations needed? (Formally: find the size of the minimum vertex cover.) Try it!