I've always found that a brief description of the Stable Marriage Problem gets people interested. I frame it as a high school dance with n boys and n girls each with a preference relation defined on the members of the opposite sex. Of course I don't call it a preference relation, but that's what it is. I then explain the disaster and heartache waiting if an unstable matching occurs.
I'll pair up people standing around at the party to illustrate the theorem, and get people involved. I'll then close with the fact that the National Resident Matching Program, which places graduating medical students into residence positions, uses the Stable Marriage Theorem to determine those placements.
The example is interesting enough to keep people listening and just technical enough that the answers aren't clear from the outset. If people are still interested you can segway into bipartite graphs and other kinds of matchings or just to graphs in general. Graph Theory is a rich area for cocktail party discussion.
NRMP Site: http://www.nrmp.org/res_match/about_res/algorithms.html
Stable Marriage Problem can be found on Wikipedia. I can't post a second link as a new user.
