# spanning tree

A *spanning tree ^{}* of a (connected) graph $G$ is a connected, acyclic subgraph

^{}of $G$ that contains all of the vertices of $G$. Below is an example of a spanning tree $T$, where the edges in $T$ are drawn as solid lines and the edges in $G$ but not in $T$ are drawn as dotted lines.