Степень вершины — число выходящих из неё рёбер. Концевая вершина имеет степень . Во всех трёх примерах ниже ровно семь подписанных вершин.
а) Возьмём цепь . Только и имеют по одному соседу; у остальных по два. Цепь связна и не имеет циклов.
б) Возьмём путь . К вершине присоединим концы , а к вершине — концы . Всего вершин. Степень имеют только , то есть ровно четыре вершины. Поскольку новые ветви оканчиваются в новых вершинах, циклов нет.
в) Соединим шесть вершин с общей вершиной . У степень , у каждой из остальных — степень . Граф связен и без циклов, значит это дерево.
