If each boy knows r girls and each girl knows r boys ,then number of boys=girls

Yet another question from BdMO 2013 Nationals:

In a class,every boy knows $r$ number of girls and every girl knows $r$ number of boys.Show that there are equal number of boys and girls[Assume that friendship is symmetric i.e. if A knows B then B knows A].

This question was set in the Secondary section of the Nationals.In the Junior Section,a similar but easier question came.

In a class,every boy knows $3$ number of girls and every girl knows $3$ number of boys.If there are 13 boys,find the number of girls in the class.

I solved this question by noting that (i)If there are 3 number of boys in the class,then number of girls also has to be 3. (ii)If there are 4 boys,required number of girls is also 4.This gives us the required tool to solve the problem.We just have to note that

$13$ boys=$(3+3+3)+4$ boys

For every 3 boys,we need 3 girls[From (i)]. Hence,(3+3+3) boys implies that there are $3+3+3=9$ girls.From (ii),we know that if there are 4 boys,we need 4 girls in the class.

Summing up,$(3+3+3)+4$ boys need $(3+3+3)+4$ girls that is 13 girls.

However,I can't see how I am going to generalize this problem.Never mind,here's my work.

MY TRY: We once again utilize the following facts:

(i)If there are 3 number of boys in the class,then number of girls also has to be 3. (ii)If there are 4 boys,required number of girls is also 4.

So if we can rewrite $r$ in the form $3k+4z$,we are done.

Lemma: Every integer $r\ge 3$ except 5 can be written in the form $3k+4z$ [k and z are positive integers,not both of them $0$]

PROOF: A number greater than or equal to 3 is of the form $3p$,$3p+1$,$3p+2$ for some positive integer p.We treat the cases individually[we must note that 5 cannot be expressed as a sum of multiples of 3 and 4.For this,we consider $p\ge 2$. So,we consider the cases r=3,4,5 separately and see that the number of boys and girls are indeed equal].

$3p$: If r=3p for some positive integer p,then plugging k=p and z=0 gives us

3p=3(p)+4(0)

and we are done.

$3p+1$: Plugging k=p-1 and z=1, we get

3(p-1)+4=3p+1

$3p+2$: Plugging k=p-2 and z=2,we get

3(p-2)+4(2)=3p+2

and the proof is complete.

Since r can always be written in the form $3k+4z$,

(1)Number of girls needed for 3k number of boys is 3k[From (i)].

(2)Number of girls needed for 4z number of boys is 4z[From (ii)].

Therefore total number of girls=3k+4z=r and we are done.Am I correct?

Let $b$ be the number of boys, and $g$ the number of girls.

For any boy $B$ and girl $G$ who know each other, write on a slip of paper "$B$ and $G$ know each other." We count the number of slips of paper in two different ways.

Since every boy knows $r$ girls, there are $br$ slips of paper.

Since every girl knows $r$ boys, there are $gr$ slips of paper.

Thus $br=gr$ and therefore $b=g$ (if $r\ne 0$).

Remark: For a more romantic version, let us suppose that each boy-girl pair who know each other kiss (once). Instead of counting slips of paper, count kisses.

Note that the relationships across gender form a bipartite graph $G$ with subgraphs $A$ (vertices are girls) and $B$ (vertices are boys). The graph is regular, that is all vertices have the same degree $r:=\deg{v}$. However, we also note that for every edge incident on a vertex on $B$, the other end of the edge is incident on $A$, since $G$ is bipartite. It follows that $\deg B=\deg A\Longrightarrow r|B|=r|A|\Longrightarrow |B|=|A|$