Graph-Theory: Find matching in bipartite graph

Question

Let $G=(V,E)$ be a graph such that $V=X\cup A\cup B$ . $X,A,B$ are independent sets and pairwise disjoint. Suppose that $|X|=63,|A|=|B|=9$, the degree of every vertex in $A\cup B$ is 7, and every vertex in $X$ has exactly 1 neighbor in $A$ and 1 neighbor in $B$. Prove there is $Y \subset X, |Y|=9$ such that for every $v\in A\cup B$ there is $y\in Y$ such that {v,y}$\in E$.

I've realized that every vertex in $A\cup B$ has exactly 7 neighbors in $X$, and that G is bipartite graph. I've tried to find $Y \subset X, |Y|=9$ such that if we'll look at the graph $G'=(A\cup B\cup Y,E')$ when every vertex in $Y$ appears twice in G', it will have a perfect matching. How can I show that? Thanks

Answer 1

By counting the number of edges between $A$ and $X$, we can first see that $X$ can be partitioned into 9 sets of size 7 each, say $R_1,R_2,\ldots,R_9$ such that each $R_i$ is the neighborhood of one element of $A$. Similarly $X$ can also be partitioned into $S_1,S_2,\ldots,S_9$ such that each $S_i$ is the neighborhood of one element of $B$.

Now we must find a set $T$ of 9 elements such that $T$ intersects all the $R_i$s and all the $S_i$s. To do this, make the auxiliary bipartite graph $H$ with one set of vertices being the $R_i$s and the other set being the $S_i$s and an edge between $R_i$ and $S_j$ if $R_i \cap S_j \neq \emptyset$. Consider the neighborhood of any $k$ $S_i$s. This should have size at least $k$ because their union has exactly $7k$ elements and hence is present in at least $k$ of the $R_i$s. Thus by Hall's theorem, $H$ has a perfect matching and we can pick one element from each of the intersections of the matched sets to obtain $T$.