Теория графов

1) Показать, что 2-реберно-связный граф G имеет хроматическое число, равное двум, если и только если G есть четный цикл или G могут быть получены из к2,3 путем разделения одного из его краев четное число раз, то есть G состоит из двух вершин, к которым присоединились и четный путь(path) два-реберных пути(paths).
2) Покажите, что задача разрешаемости о том, могут ли вершины входного мультиграфа, т. е. графа с параллельными ребрами, быть разбиты на множества A и B таким образом, чтобы между A и B было по крайней мере k ребер(k является частью входных данных), является NP-полной.
3) Покажите, что для каждого целого числа k задача разрешаемости о том, могут ли вершины входного графа G быть разбиты на множества A и B таким образом, чтобы между A и B было наименьшее расстояние, может быть решена за полиномиальное время.