spanning tree

a spanning tree of a connected graph is a subgraph that is a tree which includes all of the vertices of the graph

given $\text{[math]}$ is an undirected non-negatively weighted graph. let $\text{[math]}$ be a spanning tree, then:
$\text{[math]}$

let $\text{[math]}$ be an spanning tree of $\text{[math]}$ and let $\text{[math]}$ . upon the removal of $\text{[math]}$ from $\text{[math]}$ we get a cut (in $\text{[math]}$ ) and upon the addition of any crossing edge to $\text{[math]}$ (in place of the one we removed) we get another spanning tree for $\text{[math]}$ .

let $\text{[math]}$ be a spanning tree of $\text{[math]}$ and let $\text{[math]}$ , upon the addition of $\text{[math]}$ to $\text{[math]}$ we get a single cycle and upon the removal of any of this cycle's edges we get another spanning tree

$\text{[math]}$ spans $\text{[math]}$ and so it contains a single path $\text{[math]}$ from $\text{[math]}$ to $\text{[math]}$ . let $\text{[math]}$ the graph we get by adding a new edge $\text{[math]}$ to $\text{[math]}$ . in the graph $\text{[math]}$ there exists a cycle that contains $\text{[math]}$ and the edges from the path $\text{[math]}$ . if we were to drop from $\text{[math]}$ one of the edges of the cycle, we would get a graph $\text{[math]}$ such that $\text{[math]}$ is connected, contains no cycles and contains all the vertices of $\text{[math]}$ , which means $\text{[math]}$ is a spanning tree of $\text{[math]}$ .