Combinatorics, Hall's marriage theorem for bipartite graphs, where 2 vertices cannot be connected to more than one common vertex from the other side

Question

I have a problem I'm trying to solve. the problem is: given Bipartite graph $G=(A\cup B,E)$, where $\vert A\vert=\vert B\vert=n>100$. and all edges are from $A$ to $B$ (all edges are symmetric), additionaly, lets assume that $\forall a_1\neq a_2$ in $A$ , $$ \vert \{ b\in B : \{ a_1,b\},\{a_2,b \} \in E \} \vert \leq 1.$$ (in the original problem I had to prove it, which I actually did, So its a given now, you can also assume that the same applies with $2$ vertices of $B$ and one vertex from $A$ if you need, just like the topic mentions ). Furthermore, the degree of every vertex in A is at least $n\over4$, prove that there is a perfect matching in the graph. any hints or solutions would be great, thanks in advance!. edit: Hey, I might've done a mistake by not telling an important information, the original question included the following assumption: assume that for each $a_1 \neq a_2 $ in $A$ and for each $b_1 \neq b_2$ in $B$ at least one of the pairs $$\{a_1,b_1\},\{a_1,b_2\},\{a_2,b_1\},\{a_2,b_2 \} $$ isn't an edge in the graph.

Answer 1

Your theorem is vacuously true, since there do not exist any bipartite graphs satisfying your conditions.

Assume that a graph exists satisfying all of your conditions. On the one hand, your graph has at least $n/4$ edges for each of the $n$ vertices in $A$, so at least $n\times (n/4)$ edges in total. On the other hand, your graph has no cycles of length $3$ or $4$, which implies that it has at most $(2n)^{3/2}/2$ edges. For a proof of the general fact that a graph with $|V|$ vertices and no $3$-cycles or $4$-cycles has at most $\frac12|V|^{3/2}$ edges, see the citation at the end.

Since $n\times (n/4)\le |E|\le (2n)^{3/2}/2$, we conclude $n\le 32$, contradicting $n\ge 100$.

Garnick, David K., Kwong, Y. H. Harris, Lazebnik, Felix, Extremal graphs without three-cycles or four-cycles. J. Graph Theory 17 (1993), no. 5, 633–645. http://dx.doi.org/10.1002/jgt.3190170511