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?

$\endgroup$
  • 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 '18 at 11:51
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.

| cite | 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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