Да, обыкновенный граф – это неориентированный граф без петель и кратных ребер. Теорема вобщем-то ни при чем, просто это более точное условие гамильтоновости. Если все время надо искать полное паросочетание, то алгоритм Куна ищет его за O(n^3). Может быть, сделать какую-нибудь весовую функцию, которая делала бы одни пары более желательными, другие менее желательными, и искать полное паросочетание наименьшего веса? Или так и делают? Венгерский алгоритм делает это за O(n^4). (Все оценки из книги «Дискретная математика: матроиды, графы, алгоритмы» М.О. Асанов, В.А. Баранский, В.В. Расин, http://lib.mexmat.ru/)