# Thread: Spanning Trees

1. ## Spanning Trees

This proof was done in class and will be on the test on Friday but I just don't understand it. Can someone save me please. Thank you.

1) Prove that if T1, T2 and T3 are spanning trees of a simple connected graph G then:
d(T1, T3) <= d(T1, T2) + d(T2, T3):

2. Im sorry but the : is not suppose to be there at the end

3. Originally Posted by uniquereason81
This proof was done in class and will be on the test on Friday but I just don't understand it. Can someone save me please. Thank you.

1) Prove that if T1, T2 and T3 are spanning trees of a simple connected graph G then:
d(T1, T3) <= d(T1, T2) + d(T2, T3):
What do you mean by $d(T_1, T_2)$?

4. it is the distance between Tree 1 and Tree 2
The formula for distance between two spanning trees is |E(T1)| + |E(T2)| -2|E(T1) [intersect] E(T2)|
T1 ,T2 ,T3 are spanning trees of graph G

5. Originally Posted by uniquereason81
it is the distance between Tree 1 and Tree 2
The formula for distance between two spanning trees is |E(T1)| + |E(T2)| -2|E(T1) [intersect] E(T2)|
T1 ,T2 ,T3 are spanning trees of graph G
Well, plugging in the formula, this basically comes down to showing that for all sets $S_1, S_2, S_3$, we have

$|S_2| \geq |S_1 \cap S_2| + |S_2 \cap S_3| - |S_1 \cap S_3|$

Now, draw a Venn diagram to see what is happening, and complete...

6. Im sorry Swlabr I just don't follow how you derived that formula for that how is it showing the d(T1,T2)+d(T2,T3) is greater than or equal to d(T1,T3).

7. Originally Posted by uniquereason81
Im sorry Swlabr I just don't follow how you derived that formula for that how is it showing the d(T1,T2)+d(T2,T3) is greater than or equal to d(T1,T3).
Just take the formula for $d(T_i, T_j)$, the formula you told me, and plug it into $d(T_1,T_2)+d(T_2,T_3) \geq d(T_1,T_3)$. Cancel terms that are equal, and write $S_i$ for $E(T_i)$. That will then give you the formula I wrote.

Then, just use Venn diagrams.

8. why and how would you use a venn diagram. i am sorry for being a pain but or teacher should us a different way

9. Originally Posted by uniquereason81
why and how would you use a venn diagram. i am sorry for being a pain but or teacher should us a different way
Well, what way did your teacher teach you?

10. He did it without using the venn diagram. It was with words (if that makes any sense).

But for the venn diagram which I think I'm understanding is it two shaded circles but the middle is not.

11. Originally Posted by uniquereason81
He did it without using the venn diagram. It was with words (if that makes any sense).

But for the venn diagram which I think I'm understanding is it two shaded circles but the middle is not.
You end up with two disjoint subsets of S2 = E(T2) shaded, and so their cardinality will be less than or equal to that of S2.

If you type up what your lecturer wrote, then I can have a look at it if you want?

12. His way is CRAAAAAAAAAAZY it took up a front of a page and half of the back.
I rather learn your way which I can actually understand.

So let me give this a shot
The S_1,S_2,S_3 are basically the T_1,T_2,T_3.
Then we get the formula you got.
Next we plug that into a venn diagram
Is this venn diagram containing three circles one for each S_i.
Therefore the middle of S_1 S_2 will be shaded plus S_2 S_3
This shows that S_2 must be greater than the other two.
Is that the logic.

13. Originally Posted by uniquereason81
His way is CRAAAAAAAAAAZY it took up a front of a page and half of the back.
I rather learn your way which I can actually understand.

So let me give this a shot
The S_1,S_2,S_3 are basically the T_1,T_2,T_3.
Then we get the formula you got.
Next we plug that into a venn diagram
Is this venn diagram containing three circles one for each S_i.
Therefore the middle of S_1 S_2 will be shaded plus S_2 S_3
This shows that S_2 must be greater than the other two.
Is that the logic.
Pretty much, although you have to note that you are taking away $|S_1 \cap S_3|$. This is important because with $|S_1 \cap S_2|+|S_2 \cap S_3|$ you are essentially shading' $S_1 \cap S_2 \cap S_3$ twice. However, the $-|S_1 \cap S_3|$ gets rid of one of these shadings for you. Does that make sense?

14. Yes because the plus can means intersect.
I think if my professor would have shown us that formula it would have been easier.

15. Originally Posted by uniquereason81
Yes because the plus can means intersect.
No...the plus means' union...

Page 1 of 2 12 Last