Assume we have a simple connected graph G, how would start a prove of the following statement?
For any edge of G, there is a spanning tree of G that contans it.
I have decided that this is a true statement but I am not too sure about how to prove it. Thanks
Let $G = (V, E)$ be a connected graph, and $u v$ an arc in it. Let $T$ be a spanning tree of $G$. If $u v \in T$, there is nothing to do. If not, as $T$ is a tree, there is exactly one path from $u$ to $v$ in $T$. If an arc is deleted from this path, and the arc $u v$ is added, the result is connected and has the same number of edges as $T$, i.e., it is again a tree spanning $G$.