# Prove that there exists a set $Y$ such that for every $v$, there exists $y \in Y$ that is incident to $v$.

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\}$$.