The statistical 'impossibility' suggested in the first paragraph is perfectly feasible. Consider a population in which men engage in sex more frequently than women. Then each man might have sex with two women, but each woman with only one man. In combination with some other
statistic (e.g., that the number of sex acts per person in the same for both sexes) there might be a problem, but not the partner information alone.