3
$\begingroup$

if there are n = 2 vertices in a connected graph, i am supposed to have "n/2 edge disjoint spanning trees". This means i should have 1 edge disjoint spanning tree for a n = 2 graph?

My best guess is that if i remove the only edge between a to b, the connected graph is not disconnected. however, the only result i see from doing this is getting 2 separate disconnected graphs.

please please clarify or define to me what an "edge disjoint spanning tree" means ? When i google the term, I only get a bunch of research papers that I cannot understand. thank you very much

$\endgroup$
4
$\begingroup$

It just means that you have a set of $n/2$ spanning trees where no two trees in the set have an edge in common. So it is a property of pairs of trees, not a single tree. Thus it is trivially satisfied for the only connected graph on $n=2$ verices.

$\endgroup$
  • $\begingroup$ for each of the n/2 spanning trees, will it include all of the vertices from the connected graph ? just not all the edges? $\endgroup$ – user1476390 Feb 21 '15 at 7:11
  • $\begingroup$ Yes, that's what spanning means. $\endgroup$ – Casteels Feb 21 '15 at 7:12
  • $\begingroup$ thank you very much! i can't upvote your answer because i don't have enough rep, but if i could, i definitely would $\endgroup$ – user1476390 Feb 21 '15 at 7:14
  • $\begingroup$ i came to upvote when i had enough rep :) sorry for the delay $\endgroup$ – user1476390 Mar 12 '15 at 18:06
  • $\begingroup$ @user1476390 Thanks! If only all new users were so respectful. Welcome to the community. $\endgroup$ – Casteels Mar 12 '15 at 18:49

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.