Suppose you and your friend Alanis live, together with n?2 other people for a total of n, at a popular off-campus cooperative apartment, the Upson Collective. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so that someone cooks on each of the nights. Of course, everyone has scheduling conflicts with some of the nights (e.g., exams, concerts, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, lets label the people {p1,...,pn} and the nights {d1,...,dn}. For person pi, theres a set of nights Si ? {d1,...,dn} when they are not able to cook. 1-1Homework 5 1-2 A feasible dinner schedule is an assignment of each person in the co-op to a different night, so that each person cooks on exactly one night, there is someone cooking on each night, and if pi cooks on night dj, then dj ?? Si. (a) Describe a bipartite graph G so that G has a perfect matching if and only if there is a feasible dinner schedule for the co-op.