Too long for a comment.

For $k=2$ the answer is $a_1+a_2-\mathrm{gcd}(a_1,a_2)$, this is well known. 

The example is to take a circular cake, inscribe a regular $a_1$-gon and a regular $a_2$-gon which have $\mathrm{gcd}(a_1,a_2)$ common vertices, and use for sector partitions.

The estimate may be done as follows: if the first party is for $a_1$ women and the second for $a_2$ men, draw the edge between, say, Ann and Bob if they share a virtual piece of cake. If a connected component contains $b_1$ women and $b_2$ men, we get $b_1/a_1=b_2/a_2$ by a double counting of the cake. That yields $b_1\geqslant a_1/\mathrm{gcd}(a_1,a_2)$ and the total number of components does not exceed $\mathrm{gcd}(a_1,a_2)$. Thus the number of edges is not less than $a_1+a_2-\mathrm{gcd}(a_1,a_2)$.