Przykład 1.1
Na rysunku 12.1 przedstawiono graf niezorientowany i trzy różne drzewa rozpinające tego grafu.

Uwaga. Drzewo rozpinające grafu o n wierzchołkach ma n wierzchołków i n-1 krawędzi.

Rozważmy przykład grafu przedstawiającego sieć drogową w Polsce. Węzłami są w tym grafie miejscowości, a krawędziami drogi je łączące. Ograniczmy zbiór węzłów grafu tylko do miast wojewódzkich i postawmy sobie zadanie wytyczenia autostrad, w taki sposób by z każdego miasta wojewódzkiego można było dojechać do każdego innego miasta wojewódzkiego i tak by koszt budowy całej sieci autostrad był jak najmniejszy. Okazuje się, że rozwiązaniem może być drzewo rozpinające rozważanego grafu. Rzeczywiście struktura ta gwarantuje, że każde dwa węzły są połączone dokładnie jedną drogą. Jeśli koszty budowy autostrady między różnymi miejscowościami jest zróżnicowany, to postaramy się wybrać takie drzewo rozpinające, by suma kosztów związanych z budową poszczególnych odcinków autostrady (krawędzi) była jak najmniejsza.
Z tym samym problemem spotkamy się, gdy chcemy zbudować w sposób najbardziej ekonomiczny sieć wodociągową, okablowanie dla sieci komputerowej itd.

Definicja 1.2 Niech G będzie grafem niezorientowanym, spójnym i niech c będzie funkcją , przypisującą krawędziom grafu liczby rzeczywiste dodatnie. Nazywać ją będziemy "funkcją kosztu" dla tego grafu. Minimalnym drzewem rozpinjącym dla grafu G nazywamy drzewo rozpinające, którego suma kosztów przypisanych krawędziom (tzn. koszt drzewa rozpinającego) jest minimalna w zbiorze wszystkich drzew rozpinających tego grafu.

Uwaga Używamy tu słowa "koszt" dla funkcji przypisującej wartości krawędziom, jednak interpretacją dla wartości tej funkcji może być odległość, czas, ciężar, czy dowolny inny parametr charakteryzujący krawędz, zależnie od konkretnej sytuacji i zastosowania, w którym rzeczywistą sytuację modelujemy jako graf. W literaturze używa się nazwy "wagi krawędzi", jednak w tym kursie słowo "waga" zostało zarezerwowane dla wag wierzchołów w drzewach AVL.

Rozważmy jeszcze raz graf przedstawiony na rysunku 12.1 i przypiszmy krawędziom tego grafu koszty, por. rysunek 12.2. Wtedy koszty drzew rozpinających z rysunku 12.1 są następujące (a) -18, (b) - 31, (c) - 23.

Zastanówmy się przez chwilę, jakie założenia muszą być spełnione, by istniało minimalne drzewo rozpinające grafu niezorientowanego. Jest oczywiste, że graf, który nie jest spójny nie ma drzewa rozpinającego: istnieją w tym grafie co najmniej dwa wierzchołki, których nie można połączyć żadną drogą. Dlatego też pojęcie drzewa rozpinającego definiujemy dla grafów niezorientowanych spójnych.
Łatwo zauważyć, że graf, który ma drzewo rozpinające, może mieć więcej niż jedno minimalne drzewo rozpinające. Trywialnym przykładem jest graf, w którym funkcja kosztu jest stała: wszystkie krawędzie mają przypisaną tę samą wartość. Wtedy oczywiście jest wiele różnych drzew rozpinających. A kiedy minimalne drzewo rozpinające jest wyznaczone jednoznacznie? Odpowiedzią na to pytanie jest następujący lemat.

Niech G będzie grafem spójnym o n wierzchołkach i przypuśćmy, ze istnieją dwa drzewa rozpinające grafu G o minimalnym koszcie, T1 i T2. Niech

będą odpowiednio ciągami wszystkich krawędzi drzew T1 i T2, uporządkowanymi rosnąco ze względu na funkcję kosztu. Przyjmijmy, że i jest największym indeksem, takim że krawędzie drzew o mniejszych indeksach są identyczne, tzn. e'₁= e"₁, e'₂= e"₂, ..., e'_i-1= e"_i-1. Ponieważ funkcja kosztu jest w tym grafie różnowartościowa (z założenia) oraz krawędzie na pozycji i-tej są różne, to c(e'_i ) różni się od c(e"_i ). Niech c(e'_i ) < c(e"_i ), dla ustalenia uwagi. Ponieważ krawędz e'_i nie należy do T2, więc dołączenie jej do T2 spowoduje powstanie cyklu. Gdyby wszystkie krawędzie tego cyklu należały do T1, to w T1 też byłby cykl. Ponieważ tak nie jest (T1 jest drzewem), więc istnieje krawędz e w tym cyklu, która nie należy do T1. Wynika stąd, że krawędz e musi, w uporządkowanym ciągu wszystkich krawędzi, znajdować się na pozycji większej niż i, czyli c(e'_i ) < c(e). Rozważmy teraz graf T3, który powstaje z T2 przez odrzucenie krawędzi e i dołączenie krawędzi e'_i . T3 jest acyklicznym grafem, ma n wierzchołków i n-1 krawędzi. Jest to więc drzewo rozpinające grafu G, ale

Doszliśmy do sprzeczności z założeniem, e T2 jest minimalnym drzewem rozpinającym, co dowodzi, że w rozważanym przypadku istnieje dokładnie jedno minimalne drzewo rozpinające grafu.

Na zakończenie tego punktu zwróćmy uwagę, że minimalne drzewo rozpinające grafu nie musi być drzewem najkrótszych ścieżek z pewnego ustalonego wierzchołka. Na rysunku 12.2(a) przedstawiono drzewo najkrótszych ścieżek z wierzchołka A. Jest to oczywiście drzewo rozpinające grafu. Nie jest jednak minimalne. Minimalne drzewo rozpinające tego grafu przedstawiono na rysunku 12.2(b). Oczywiście, mamy tu ścieżki z A do każdego wierzchołka, ale niekoniecznie najkrótsze.

Pytanie 2: Jeżeli D jest drzewem rozpinającym pewnego acyklicznego i spójnego grafu niezorientowanego o m krawędziach, to ile wierzchołków ma to drzewo?