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?

  • 3
    $\begingroup$ You've not written even an informal proof: essentially, you've said "I think the answer is yes, because the answer is yes." $\endgroup$ Commented Jan 25, 2018 at 11:51

2 Answers 2


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.

  • $\begingroup$ That's exactly what I said! $\endgroup$ Commented May 26, 2019 at 18:00
  • 2
    $\begingroup$ Yes, but I said it with fewer words. :) $\endgroup$
    – mo2019
    Commented May 27, 2019 at 8:42
  • $\begingroup$ 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. $\endgroup$ Commented May 27, 2019 at 10:11
  • 1
    $\begingroup$ Then please read the existing answers before posting one of your own. $\endgroup$ Commented May 27, 2019 at 16:36
  • 1
    $\begingroup$ Nothing is really required -- how could we enforce it, anyway? But it is generally expected that answers should contribute something new, and how can you know you're doing that if you don't know what's already beed said? Having multiple answers that all say the same thing just clutters the page, though obviously that's not a big deal with just two. Posting a short, summary-style answer can definitely be valuable when the existing answers are long; I just don't think it adds anything in this particular case. $\endgroup$ Commented May 27, 2019 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.