= Spanning tree
{wiki}
A <spanning tree> of a <connected graph> $G$ is a <subgraph> that is a <tree> and contains every <vertex> of $G$. Its <edges> must come from $G$. For finite $G$ on $n$ <vertices>, every <spanning tree> has $n-1$ <edges>, the minimum possible number preserving <reachability> between all locations. This makes a <spanning tree> a compact certificate that the original <graph> is connected. A <minimum spanning tree> additionally minimizes a specified total <edge> weight; merely selecting a <spanning tree> supplies no such optimization. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf[MIT, Mathematics for Computer Science, sections 11.10.3–11.10.4]{ref}
Let $G$ be our seven-<vertex> <tree> with <edge> $57$ added. It has seven <edges> and a <graph cycle>. Removing $57$ gives the original <spanning tree> $T$; removing $13$ instead gives another <spanning tree> $T'$. Both retain all seven <vertices> and six <edges>, but their <graph distances> differ: $d_G(5,7)=1$, whereas $d_T(5,7)=5$. In $T'$, $d_{T'}(5,7)=1$ but $d_{T'}(1,3)=5$, along $1,2,5,7,6,3$, compared with $d_G(1,3)=1$. Preserving <reachability> permits longer journeys; <breadth-first search> can preserve <graph distances> from one chosen starting <vertex>.
\Image[/spanning-tree-cycle-exchange.png]
{title=Two <spanning trees> preserve <reachability> but change different <graph distances>}
To construct a <spanning tree>, repeatedly delete any <edge> on a <graph cycle>. Its endpoints remain joined through the rest of that <graph cycle>, so the deletion preserves connectedness. Finiteness ensures that this stops at a connected <acyclic graph>. Conversely, adding an omitted <edge> to a <spanning tree> creates its unique <fundamental cycle>; deleting any other <edge> on that <graph cycle> produces another <spanning tree>. The displayed exchange replaces $13$ by $57$. https://www.maths.tcd.ie/~dwilkins/Courses/MA2C03/MA2C03Courseware_2014to15/MA2C03_S4_Yr1415.pdf[Trinity College Dublin, section 4.16: deleting cycle edges preserves connectivity]{ref}
Back to article page
