Если изобразить всех людей в виде точек и между знакомыми провести соединительные линии, то получится граф знакомств. В этом графе требуется выделить максимальное число взаимно не пересекающихся ребер. Это известная задача нахождения максимального парасочетания в графе. Ее решение можно найти в литературе, например, Н. Кристофидес, Теория графов. Алгоритмический подход. - М., Мир, 1978.

Эта задача, вообще говоря, переборная. Вопрос заключается только в том, насколько эффективно этот перебор осуществляется. О некоторых приемах перебора вариантов, в частности, о поиске с возвращением, можно прочесть в книге Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы. Теория и практика. - М., Мир. 1980.