Wir führen Induktion über die Anzahl der Kanten. Der Induktionsanfang ist klar, da ein kantenfreier Graph nur im einpunktigen Fall zusammenhängend ist, und dies ein Baum ist. Sei ${\displaystyle {}G=(V,E)}$ ein zusammenhängender Graph mit ${\displaystyle {}m}$ Kanten. Wenn ${\displaystyle {}G}$ ein Baum ist, sind wir fertig. Sei also ${\displaystyle {}G}$ kein Baum. Dann gibt es einen Kreis

${\displaystyle v_{1},v_{2},\ldots ,v_{r},v_{r+1}=v_{1}}$

mit ${\displaystyle {}r\geq 3}$ in ${\displaystyle {}G}$. Wir betrachten den Graphen ${\displaystyle {}G'}$ mit der gleichen Knotenmenge ${\displaystyle {}V}$ und der neuen Kantenmenge

${\displaystyle {}E'=E\setminus \{v_{1}v_{2}\}\,.}$

Dieser Graph hat eine Kante weniger und er ist zusammenhängend, da der Zusammenhang zwischen ${\displaystyle {}v_{1}}$ und ${\displaystyle {}v_{2}}$ über das verbleibende „Kreissegment“ ${\displaystyle {}v_{2},\ldots ,v_{r}=v_{1}}$ gesichert ist. Nach Induktionsvoraussetzung gibt es einen aufspannenden Baum in ${\displaystyle {}G'}$, und dieser ist auch ein aufspannender Baum von ${\displaystyle {}G}$.