Определение на граф:
Граф ще наричаме всяко крайно множество от точки или върхове, някои от които са свързани помежду си с линии, които наричаме ребра.

Математически графът се обозначава като двойка (V,G), където V е множеството от върховете му, а G е множество от връзките между тях (ребрата).

Ако x и y са два върха от графа, свързани с ребро, това ребро ще обозначаваме така:

• с <x,y> и ще го наричаме ориентирано ребро, когато има значение редът на върховете във връзката.
  Ако си представяме ребрата като пътища, свързващи върховете на графа, ориентираното ребро <x,y> е еднопосочен път - можем тръгнем от върха x и по това ребро да стигнем до y, но не и да се движим в обратно направление.
• с (x,y) и ще го наричаме неориентирано, когато връзката е симетрична, т.е. няма значение редът на върховете.
  Ако си представяме ребрата като пътища, неориентираното ребро (x,y) е двупосочен път - можем тръгнем от върха x и по това ребро да стигнем до y, както и да се движим в обратно направление.

Когато не е посочено изрично какви ребра съдържа графът, ще приемаме, че всички те са неориентирани.

Определение на път (маршрут):
Път или маршрут в графа G ще наричаме поредица от върхове i₀, i₁, ... i_k, такава, че всеки два поредни върха са свързани с ребро, като ребрата не се повтарят.

Определение на свързан граф:
Един граф е свързан, могато между всеки два негови върха има път.

Определение на цикъл:
Цикъл в графа G е път, за който началният и крайният връх съвпадат.

Определение на гора:
Гора е граф, в който няма цикли.

Определение на дърво:
Дърво е гора, в която между всеки два върха има път.

Понятията път и цикъл имат смисъл както за ориентирани, така и за неориентирани ребра (сътветно графи с такива ребра), докато определенията за гора и дърво дърво са смислени в този си вид само за графи с неориентирани ребра.

Лема Tree_1:
Между всеки два върха на дървото има единствен път.

Доказателство (идея):
Допуснете че има двойки върхове с поне 2 пътя между тях.
Изберете от тях двойката с минимален брой ребра по 2 от пътищата.
Докажете, че тези два пътя образуват цикъл.

Лема Tree_2:
Нека T е дърво с поне 2 върха. Тогава в T има връх от който излиза точно 1 ребро.

Доказателство (идея):
Тъй като T е с поне 2 върха, от всеки връх излиза поне 1 ребро.
Допуснете, че от всеки връх излизат поне 2 ребра.
Тръгвайки от кой да е връх по две от ребрата му и използвайки факта, че броят на върховете е краен, постройте цикъл.

Лема Tree_3:
Нека T е дърво с n върха. Тогава в T има n-1 ребра.

Доказателство (идея):
Използвайте индукция по броя на върховете и предната лема.