Suppose $A,B,X$ are independent and disjoint sets of vertices in a graph such that $A \cup B \cup X = V$, $|A|=|B|=9$ and $|X| = 63$. Also, assume $d(v) = 7$ for every $v \in A,B$ and suppose that for every $x \in X$, $x$ is incident to exactly one $a \in A$ and one $b \in B$. Prove that there exists a set $Y \subseteq X$ such that for every $v \in A \cup B$, there exists $y \in Y$ such that $y$ is incident to $v$, and $|Y|=9$.
I tried to solve using the pigeonhole principle but the numbers didn't work. Any ideas?
Let $G$ be the given graph and $G’$ be an auxiliary bipartite graph with vertex parts $A$ and $B$ where vertices $a\in A$ and $b\in B$ are adjacent iff there exists a vertex $x\in X$ adjacent in $G$ to both $a$ and $b$. We claim that $G'$ has a perfect matching. To show this we have to check that $G'$ satisfies the conditions of Hall’s Marriage Theorem. Let $W$ be a subset of $A$. Then in $G$ there are $7|W|$ edges incident to vertices of $W$. Each of these edges has a unique adjacent edge of a form $(x,b)$ with some $x\in X$ and $b\in B$. Then clearly $b\in N_{G’}(A)$. Since any vertex $b\in B$ can participate in at most $7$ pairs $(x,b)$ for some $x\in X$, $|N_{G’}(A)|\ge 7|W|/7=|W|$. Let $M$ be a perfect matching for $G’$. Then $M$ consists of $|A|=|B|=9$ edges and for each edge $(a,x)\in M$ there exists a vertex $v(e)\in X$ such that $(a,x)$ and $(x,b)$ are edges of the graph $G$. It remains to put $Y=\{ v(e):e\in M\}$.