Задача по теории графов

[Гость]

Помогите, пожалуйста, решить задачу по теории графов.

Имеется несколько юношей, каждый из которых знаком с некоторыми девушками. Две свахи знают, кто с кем знаком. Одна сваха заявляет: "Я могу одновременно женить всех брюнетов так, чтобы каждый из них женился на знакомой ему девушке!". Вторая сваха говорит: "А я могу устроить судьбу всех блондинок: каждая выйдет замуж за знакомого юношу!". Этот диалог услышал любитель математики, который сказал: "В таком случае можно сделать и то, и другое!". Прав ли он?

[Гость]

Вроде бы задача простая. Но решить не так-то просто. Она, кажется, из какой-то олимпиады. При том за ее решение давали 5 или 6 очков, так что там она считалась трудной.

[Evgeni_1003]

Задача-то совсем простая.
Рассмотрим граф с вершинами людьми и направленными ребрами ( из брюнетов к их невестам и из блондинок к их женихам).
Так как в каждую вершину входит не более одного ребра и выходит не более одного, то все ребра можно разбить на направленные циклы и пути не пересекающиеся по вершинам. Так как они не пересекаются по вершинам, то для каждого из них можно решать задачу отдельно.

Например, выбрав ребер через одно ( циклы имеют четную длину, а в пути надо выбирать 1-е, 3-е, ... ребра, считая от начала) получаем пример свадеб.