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|$

64 Views Asked by At

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.

Thanks in Advance.