METU Department of Mathematics Math 405 Combinatorics Spring 2010

QUIZ 6

Problem 1. Consider subsets of {1, 2, 3, 4}, A_{1} = {1, 2}, A_{2} = {2, 3, 4}, A_{3} = {1, 3}, A_{4} = {3, 4}.

(1) Sketch the incidence graph between the elements and the subsets.

(2) Find the corresponding incidence matrix.

(3) Is the Hall marriage condition satisfied for these set of subsets ? Give your reason.