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.

  • 1
    $\begingroup$ Did you miss a condition here? The edgeless graph (say, with 16 vertices) is a counterexample. $\endgroup$ – 79037662 Oct 9 at 18:15
  • $\begingroup$ Could you please explain how come a disconnected graph is a counter-example? $\endgroup$ – user730119 Oct 9 at 18:22
  • $\begingroup$ It contains vertices which do not have degree $n^{3/4}$...? $\endgroup$ – 79037662 Oct 9 at 18:22
  • $\begingroup$ then the graph is not bipartite too I guess. $\endgroup$ – user730119 Oct 9 at 18:25
  • $\begingroup$ What is your definition of bipartite graph? $\endgroup$ – 79037662 Oct 9 at 18:25

Your Answer

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

Browse other questions tagged or ask your own question.