Is every edge of a graph included in some spanning tree?

Let's say we have a graph $G$. We pick one edge from it (any edge). Will there always be such a spanning tree that contains that very edge?

I think the answer is yes, because no matter what we do we can always create such a spanning tree so that the very edge we picked is included. Of course, a more formal proof would be needed?

• You've not written even an informal proof: essentially, you've said "I think the answer is yes, because the answer is yes." – David Richerby Jan 25 '18 at 11:51

Note that the initial graph $G$ needs to be connected or it has no spanning trees at all. (Though the same argument applied to each component would show that any graph has a spanning forest containing any chosen edge.)

Let $G=(V,E)$ be a connected graph, let $T$ be any spanning subtree and let $e$ be any edgein $E$. We claim that there is a spanning tree that includes $e$. If $e\in T$, we are done. Otherwise, $T+e$ contains a cycle. That cycle necessarily contains at least one edge $e'\neq e$ (actually, it contains at least two). $T+e-e'$ is a spanning tree that contains $e$.

You should prove to yourself that $T+e-e'$ really is a spanning tree.

Adding an edge to a tree causes a unique cycle. You can remove any edge from this cycle (different from the one you added) to get back a tree. This new tree contains the edge that was added.

• That's exactly what I said! – David Richerby May 26 '19 at 18:00
• Yes, but I said it with fewer words. :) – mo2019 May 27 '19 at 8:42
• Because my seven sentences really need to be summarized into three. We have five thousand unanswered questions on the site -- it would be much better to answer some of those than to post duplicate answers to questions that don't need them. – David Richerby May 27 '19 at 10:11