Задание 1. Заполните таблицу. Выберите обязательные пункты для каждого определения из 1 столбца. Ребро не может быть вершиной; также является вершиной грани, из которой выходит только одно ребро, называется висячей. Терема 1. О единственности дуги. Между любыми двумя вершинами дерева существует единственный путь, который их соединяет. Теорема 2. О существовании висячей вершины. В любом дереве, в котором более одной вершины, есть вершина, из которой выходит ровно одно ребро, т. е. вершина является висячей. Теорема 3. О связи между числом вершин и рёбер. В дереве количество вершин на 1 больше количества рёбер, то есть n = m + 1, где n — количество вершин, m — количество рёбер. Дерево — связный граф без циклов, который показывает наглядность и позволяет учесть все варианты.

В заполненной таблице «+» отмечает обязательный пункт, «−» — не обязательный.

Единственный путь в дереве не повторяет вершины и не замыкается в цикл. Висячая вершина имеет ровно одно инцидентное ребро. В дереве с n вершинами число рёбер равно n − 1; ограничения на повтор вершин в формулировке этой теоремы не нужны.