A number of boys and a number of girls attend a ballroom dancing party. The rule is that only a boy and a girl can dance together, and the pair is fixed for the whole party (i. e. if a boy dances with a certain girl, then he cannot dance with other girls; vice versa). Some dancing pairs are possible (e. g. because they like each other) and other dancing pairs are not possible. The problem is to form the largest number of pairs that can dance.

For instance, in the figure of Example 1 below, there are three boys and four girls. The line between 1 on the left side and 3 on the right side means that the first boy and the third girl can form a dancing pair. Other lines have similar meanings. There is no line between 1 on the left side and 2 on the right side, which means that the first boy and the second girl cannot form a dancing pair.

(a) Consider the problem of finding the maximum number of dancing pairs for the setting in Example 1 below. Formulate the problem as an integer linear program (ILP). Write explicitly what the data are, what the decision variables are, what the objective function is, and what the constraints are.

(b) Consider the problem of finding the maximum number of dancing pairs for the setting in Example 2 below. Formulate the problem as an integer linear program (ILP). Write explicitly what the data are, what the decision variables are, what the objective function is, and what the constraints are.

(c) We say the LP relaxation of an ILP problem is tight if the LP relaxation of the ILP (i. e. discard the integer constraints in the ILP to get an LP) has the same optimal value as the ILP. If you think the LP relaxation of your formulation in (b) is tight, explain your reason. If not, please write another ILP problem (perhaps a small variant of your original ILP formulation) so that the LP relaxation of your formulation is tight. Explain the reason why its LP relaxation is tight.