Let $\Gamma$ be a finite connected bipartite graph with colour classes $U$ and $V$ such that:

  • every vertex of $U$ has degree $n$, and $n\ge 3$;
  • every vertex of $V$ has degree at least $4$;
  • $\Gamma$ has diameter $4$;
  • for every vertex $u$ of $U$, there are at least $(n+1)/2$ vertices in the neighbourhood $\Gamma(u)$ of $u$ that have degree the minimum degree of $\Gamma(u)$.

Is $\Gamma$ biregular (i.e., the vertices of $V$ have constant degree)? If not, then under what natural and weak conditions is biregularity forced to hold?


I tried to construct an example that is not biregular. To make it easy, I assumed that n=3 and that the vertices of V all have degree 4 except one of degree 5 (so each vertex of U is automatically adjacent to at least two vertices of degree 4).

One option where the numbers work out is to have 7 vertices in U and 5 vertices in V, so if I set V = {A,B,C,D,E} and then make the 7 neighbourhoods equal to {ABC, ABD, ABE, ACE, ADE, BCD, CDE} then I think that vertex A has degree 5, and all the others degree 4.

I don't know what sort of condition you'd need to rule out examples like this..

  • $\begingroup$ This example has small girth (=4), so is it possible to construct an example of girth 6? By the way, if the girth is 8, then it is well known that the graph is biregular (because then, we would have a thick generalised quadrangle). $\endgroup$ – John Bamberg Dec 17 '16 at 0:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.