Теория:

В теории графов деревом называется связный граф без циклов. Но, взглянув на любое дерево на улице, можно заметь, что ветви похожи на ребра графа, а точки где эти ветви соединены — на вершины графа. Вот и получается именно тот граф без циклов.
 
Деревья — это те графы, с которыми вы в курсе информатики, да и других предметов, чаще всего имеете дело. Применяя алгоритмы поиска в глубину или в ширину, вы из исходного графа извлекаете дерево — вершинами в нем являются вершины исходного графа, и эти вершины соединяются ребром, если при исполнении алгоритма переход от одной вершины к следующей осуществлялся по этому ребру.
Пример:
К графу, изображенному на рисунке 1, применим алгоритм поиск в глубину.
 
а1.png
Рис. 1
 
Получим при этом обходе графа дерево, изображенное на рисунке 2.
 
а2.png
Рис. 2
 
К графу, изображенному на рисунке 3, применим алгоритм поиск в ширину.
 
б1.png
Рис. 3
  
Получим при этом обходе графа дерево, изображенное на рисунке 4.
 
б2.png
Рис. 4
Дерево, которое содержит все вершины некоторого заданного графа \(G\) и ребра которого являются ребрами этого графа, называется каркасом графа \(G\). По-другому каркас называют остовом или стягивающим деревом.
Дерево изображается по правилу: 
  1. фиксируют одну из вершин, ее называют корнем;
  2. корень изображаем внизу, а все остальные вершины распределяют по уровню;
  3. на первом уровне размещаются вершины, смежные с корнем;
  4. на втором уровне размещаются вершины, смежные с вершинами первого уровня, отличные от корня;
  5. на третьем уровне размещаются вершины, смежные с вершинами второго уровня, отличные от вершин первого уровня, и т.д.
Пример:
Для графа, изображенного на рисунке 5, построим одно и то же дерево при разном выборе корневой вершины.
 
в2.png
Рис. 5
 
В первом случаи корнем служит вершина, обозначенная числом 0.
 
в3.png
Рис. 6
 
Во втором случаи корнем служит вершина, обозначенная числом 11.
 
в4.png
Рис. 7
Утверждение 1.  В любом дереве вершин графа всегда на \(1\) больше, чем ребер.
Утверждение 2. Если в связном графе количество вершин на \(1\) больше числа ребер, то это — дерево.
Источники:
Гейн А.Г., Сенокосов А.И. Информатика и ИКТ: учебник для общеобразовательных учреждений. - Москва: Просвещение, 2012. -235 с.