C# Реализовать код по Двудольным графам

Нужно написать код по реализации взвешанного двудольного графа.

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

После граф проверяется на двудольность и если он двудольный - тогда выполняется дальнейшая работа с ним. Проверку на двудольность можно выполнить с помощью поиска в глубину. Затем уже граф разделяется на две доли.

Из методов нужен: показать вершины в каждой доле, соединены ли две вершины, поиск паросочетания с наименьшим весом, поиск паросочетания с наибольшим весом.

Желательно добавить комментарии и описать алгоритм работы для понимания кода.

Также прикрепил пример кода main, как должен примерно выглядеть код.