Hmm.. I think there is a straightforward proof but is it not a direct consequence of Hall's theorem? Pierre.

pbornsztein wrote: Hmm.. I think there is a straightforward proof but is it not a direct consequence of Hall's theorem? Pierre. Hall's theorem only applies to bipartite graphs.

Groumpf.. Well, the graph whose vertices are the persons and any edge connect two of them if and only if they can have a conversation has an hamiltonian cycle, because each vertex has degree at least $4$, so that it satisfies Dirac's condition. To find the desired pairing, you only have to cut the hamiltonian cycle into appropriate pairs. Pierre.

Here's another (clumsier) way: Suppose that no such grouping exists; that is, every grouping has at least one pair of people who can't talk to each other. We show that at least one person can't talk to more than 3 people. Call a pair of people "forbidden" if they can't talk to each other. There are $\frac{{{8}\choose{2}}{{6}\choose{2}}{{4}\choose{2}}}{4!}= 105$ possible groupings. Label the people from 1 to 8. WLOG assume that 1 and 2 can't talk to each other. There are $\frac{{{6}\choose{2}}{{4}\choose{2}}}{3!}=15$ groupings that contain the pair (1 2). Similarly, there 15 - 3 = 12 additional groupings that contain the pair (3 4), 10 additional groupings containing the pair (5 6), and 8 additional groupings that contain the pair (7 8). We continue the process of constructing "forbidden" pairs until every person can't talk with 3 other people. Eventually we find that there are 15+12+10+8+10+7+5+3+5+5+5+5+5+5 = 100 groupings containing these pairs (just some counting). But there are 105 groupings in total, so there is at least one more "forbidden" pair. Contradiction.

see here: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=151&t=47785&