# Prove that there exists a bipartite graph $G(A, B, E)$ such that every vertex in set $A$ has degree $n^{3/4}$ if $|A| = |B|$

Prove that there exists a bipartite graph with vertex set $$V = A \cup B$$, where $$|A| = |B| = n$$, such that all vertices in set $$A$$ have degree $$n^{3/4}$$ and all vertices in $$B$$ have degree at most $$3n^{3/4}$$.

Also, every subset of $$A$$ of size $$n^{3/4}$$ should have at least $$n - n^{3/4}$$ neighbours in $$B$$.

I know I can solve this problem using the property p1: sum of the degrees of the vertices in $$A$$ equals the sum of the degrees of vertices in $$B$$.

I need to prove that a bipartite graph can be created which will satisfy the above two properties.

• It contains vertices which do not have degree $n^{3/4}$...? – 79037662 Oct 9 at 18:22