This is all based on unfounded assumptions about who has sex with whom. If you make a graph in which vertices are people and two people have an edge between the

This is all based on unfounded assumptions about who has sex with whom. If you make a graph in which vertices are people and two people have an edge between them if they've had sex, then the structure you actually get is surprising. Here's a real sex graph; bear in mind that this is from a high school, so the things I say in the rest of the post may not apply outside high schools and colleges: http://www.soc.duke.edu/~jmoody77/chains_pressfigure1.jpg http://www.soc.duke.edu/~jmoody77/chains_pressfigure1.jpg You've got a lot of two-person monogamous pairings, a smaller number of triads, scattered chains, and then this BIG, HAIRY THING that's vaguely ring-shaped. It doesn't have promiscuous hubs; you can stop the spread of STDs by trying to get as many people as possible to use condoms and get STD screening, thus breaking the chains. It's almost a spanning tree. This structure can be generated from two simple rules: 1. People tend to date other people with a similar amount of past sexual experience. 2. People avoid dating the exes of other people who are close to them in the relationship graph, since this makes them look bad to their friends, exes, and so on. This accounts for the lack of short cycles. This was theoretically confirmed by some researchers who wrote computer simulations to try to come up with similar-looking relationship graphs, and succeeded brilliantly: http://www.soc.duke.edu/~jmoody77/chains.pdf http://www.soc.duke.edu/~jmoody77/chains.pdf