Деревья в теории графов

Задача1)

Докажите, что существует ровно шесть неизоморфных деревьев с шестью вершинами и одиннадцать - с семью вершинами.

Задача2)

Докажите, что графы, соответствующие (в смысле упражнение 1b) насыщенным углеродам C_n H_(2n+a) и спиртам C_n H_(2n+a) OH, являются деревьями.

Задача3)

Найдите остовное дерево и ассоциативные с ним фундаментальные системы циклов и разрезов следующих графов:

(I) K5; (II) K3,3; (III) W5; (IV) Cв; (V) Платоновых графов; (VI) графа Петерсена.

Задача4)

Пусть А – матрица инциденций дерева с n вершинами. Докажите, что любые n – 1 столбов матрицы А линейно независимы над полем целых чисел по модулю 2.

С подробным доказательством.