Biparted graph uniqueness

Question

There is a bipartite graph with parts $X$ and $Y$ such that:

1. $Y$ has 20 nodes
2. Each node in $X$ is connected to 8 nodes in $Y$ uniquely (i.e. the set of adjacents for each node in $X$ is unique).

I want to prove that we can connect each node in $X$ to another node in $Y$ such that the resulting graph will still satisfy (2).

Answer 1

Let $\mathcal{F} $ be a familly on $9$ element subsets in $Y$ and let $x_1,x_2,...,x_n$ be a vertices in $X$. Then make new bipartite graph between $\mathcal{F} $ and $X$ so that vertex $x_i$ is connected to $F\in \mathcal{F} $ iff $N(x_i) \subseteq F$. Now try to prove there is a perfect matching.

Every node in $X$ has degree $12$ and every set $F\in\mathcal{F} $ has degree at most $9$.

Now this does work, use the result I most recently proved here: Hall's marriage theorem in bipartite graph

Answer 2

Hint : Connect each node $x \in X$ to one of the nodes in $Y$ farthest from $x$. Consider distance between $x$ and $y$ to be infinity if there's no path connecting them.