Since it is irrelevant which persons of the same gender know each other, we may assume there ore none such, and consider the bipartite graph $G$ having the left shore made of the $n$ boys and the right shore made of the $m$ girls, with an edge connecting a boy and a girl if they know each other. The condition means $G$ does not contain any induced $C_4$ cycle of length $4$, and the requirement is to show the number $E$ of edges satisfies $E \leq m + \dfrac {n(n-1)} {2}$. Thus it is an extremal graph theory question, for bipartite $(n,m)$ graphs with forbidden $C_4$'s; by symmetry we should also have $E \leq n + \dfrac {m(m-1)} {2}$. Denote by $A$ the set of girls that each knows exactly one boy, and by $B$ the set of girls that each knows more than one boy; take $a=|A|$ and $b = |B|$. We obviously have $a+b\leq m$ and $E= a + \sum_{g\in B} \deg g$. Let us count the number $N$ of objects $\{g, \{b_1,b_2\}\}$, where $g\in B$ is a girl, $b_1,b_2$ are distinct boys, and $g$ knows both $b_1,b_2$. For each of the $\dfrac {n(n-1)} {2}$ doubletons $\{b_1,b_2\}$ there is at most one girl $g$ knowing them both (by the condition), so $N \leq \dfrac {n(n-1)} {2}$. Moreover, by pigeonhole we have $b\leq \dfrac {n(n-1)}{2}$. On the other hand, we have $N = \sum_{g\in B} \dfrac {\deg g(\deg g - 1)} {2} \geq$ $ \dfrac {b} {2} \dfrac {\sum_{g\in B} \deg g} {b} \left ( \dfrac {\sum_{g\in B} \deg g} {b} - 1\right ) =$ $ \dfrac{(E-a)((E-a) - b)} {2b}$, by Jensen's inequality. We thus need $(E-a)^2 - b(E-a) - bn(n-1) \leq 0$, so $E-a \leq \dfrac {b + \sqrt{b^2 + 4bn(n-1)}} {2} \leq$ $ \dfrac {b + \sqrt{b^2 + 2bn(n-1) + (n(n-1))^2}} {2} =$ $ \dfrac {b + (b + n(n-1))} {2} =$ $ b + \dfrac {n(n-1)} {2}$. Finally, we get $E \leq a+ b + \dfrac {n(n-1)} {2} \leq m + \dfrac {n(n-1)} {2}$. For equality to be reached we obviously need $b= \dfrac {n(n-1)} {2}$, namely for each pair of boys having exactly one girl knowing both of them; and then we need $a = m-b$.

Another solution: Consider the bipartite graph where there are girls $G$ and boys $B$ and denote the girls by $g_i$'s and boys by $b_i$'s as vertices. Let $x_i$ denote the number of edges from the vertex $g_i$ to set $B$. If $g_i$ is connected to some $b_k$ and $b_\ell$ then for any $j \neq i$ the girl $g_j$ must not connected to both $b_k$ and $b_\ell$. Now let us count such pairs. For every girl $g_i$ there are $\dbinom{x_i}{2}$ many pair of edges. Since all such edge pairs must be distinct for all girls, and since there are at most $\dbinom{n}{2}$ such pairs, we have \[ \dbinom{x_1}{2}+\dbinom{x_2}{2}+\ldots+\dbinom{x_m}{2} \leq \dbinom{n}{2} \] or equivalently \[ x_1^2+x_2^2+\ldots+x_m^2-(x_1+x_2+\ldots+x_m) \leq n^2-n \] Now assume that $x_1, x_2, \ldots, x_k$ are greater than or equal to $2$ and $x_{k+1}, x_{k+2}, \ldots, x_m$ are $0$ or $1$. Then we have \[ x_1^2+x_2^2+\ldots+x_k^2-(x_1+x_2+\ldots+x_k) \leq n^2-n \] and we need to show that $x_1+x_2+\ldots+x_k \leq k+\dbinom{n}{2}$. Since $x_i \geq 2$ for $1 \leq i \leq k$ we have $x_i^2-x_i \geq 2$ and hence $2k \leq n^2-n$. Now by Cauchy-Schwarz inequality we have \[ x_1^2+x_2^2+\ldots+x_k^2 \geq \frac{(x_1+x_2+\ldots+x_k)^2}{k} \] and if $x_1+x_2+\ldots+x_k=A$, we have \[ \frac{A^2}{k}-A \leq n^2-n \] and we need to show that $A \leq k+ \dbinom{n}{2}$. Assume $A > k+\dbinom{n}{2}$. Then we have \[ k(n^2-n) \geq A(A-k) > \left[k+\dbinom{n}{2}\right] \cdot \dbinom{n}{2} \] which means that $2k > n^2-n$ which is a contradiction. So, we are done.

Lets call boys $(B{}_i){}_{i=1,...,n}$ and girls $(G{}_i){}_{i=1,...,m}$. Now set $S{}_{B{}_k}=\{G_i/ G{}_iB{}_k=1 \}$ (1 means they know each other...). It's clear that any two different sets $S_B$ have at most one element in common else we will breach problem's condition. if we call $\pi$ the set of unordered pairs (boy,girl) that know each other then $\#(\pi)= \sum^n_{k=1} \#(S{}_{B{}_k}) \leq \# (\cup^n_{k=1} S{}_{B{}_k}) + \sum_{i<j} \# (S{}_B{}_i \cap S{}_B{}_j) \leq m + \dbinom{n}{2} $

The problem reformulated is just a bipartite graph with the partitioned vertex sets of size $m,n$,that lacks a $K_{2,2}$. The problem follows by double counting triples (A,B,C),where boys $A,B$ know girl $C$.

The conditions imply that for any two boys, they know at most one girl. Let $x_i$ be the number of girls that know exactly $i$ boys. Then $\sum_{i=1}^n{x_i}=m$. Thus counting the pairs of two boys and one girl we see that $$\sum{\frac{i(i-1)}{2}x_i} \leq \frac{n(n-1)}{2}.$$Thus the number of boy-girl pairs is $$\sum_{i=1}^n{ix_i}=m+\sum_{i=2}^n{(i-1)x_i}\leq\sum{\frac{i(i-1)}{2}x_i} \leq \frac{n(n-1)}{2}$$as desired.

Very weird problem. Label the bipartitions as $A$ and $B$ with $A$ having $m$ vertices. Let $x_1, x_2, \dots, x_m$ be the degrees of the $m$ vertices, and assume WLOG that $x_i \geq 2$ for each $i$. (If otherwise, just neglect the vertices that have degree $1$ and look at the rest.) By Jensen inequality $$m{\frac{|E|}m \choose 2} \leq \sum_{i=1}^m {x_i \choose 2} \leq {n \choose 2},$$as any two vertices in $B$ share at most one common neighbor. Now I claim that ${n \choose 2} \geq m$. This is clear, as if otherwise, we would have $$m > \sum_{i=1}^m {x_i \choose 2} \geq \sum_{i=1}^m 1 = m.$$But if $|E| > m+{n \choose 2}$, we have $$\frac{n(n-1)(2m+n(n-1))}{4m} > n(n-1),$$which is an obvious contradiction.

If we view $C_4$ as $K_{2,2}$ then this problem becomes trivial. Double count triples $(u_1,u_2,v)$ where $u_1$, $u_2$ belong to the ``$n$" subset and $v$ belongs to the ``$m$" subset. This readily gives us \[\binom{n}2 \geq \sum_{i} \binom{\deg v_i}2 \geq \sum_i \deg(v_i)-1=E-m\]where $E$ is the number of edges.