3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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$
    – David Richerby
    Jan 25, 2018 at 11:51

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ That's exactly what I said! $\endgroup$
    – David Richerby
    May 26, 2019 at 18:00
  • 2
    $\begingroup$ Yes, but I said it with fewer words. :) $\endgroup$
    – mo2019
    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$
    – David Richerby
    May 27, 2019 at 10:11
  • 1
    $\begingroup$ Then please read the existing answers before posting one of your own. $\endgroup$
    – David Richerby
    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$
    – David Richerby
    May 27, 2019 at 16:54

Your Answer

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

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