1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.