Do any two spanning trees of a simple graph always have some common edges?
up vote
1
down vote
favorite
I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to prove or disprove this conjecture?
graphs graph-theory spanning-trees
add a comment |
up vote
1
down vote
favorite
I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to prove or disprove this conjecture?
graphs graph-theory spanning-trees
Assuming the weights of the graph are distinct, the edge with the minimum weight will be present in all the minimum spanning trees.
– Gokul
1 hour ago
@Gokul minimum spanning tree? What?...
– Mr. Sigma.
34 mins ago
Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
28 mins ago
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to prove or disprove this conjecture?
graphs graph-theory spanning-trees
I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to prove or disprove this conjecture?
graphs graph-theory spanning-trees
graphs graph-theory spanning-trees
asked 1 hour ago
Mr. Sigma.
348116
348116
Assuming the weights of the graph are distinct, the edge with the minimum weight will be present in all the minimum spanning trees.
– Gokul
1 hour ago
@Gokul minimum spanning tree? What?...
– Mr. Sigma.
34 mins ago
Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
28 mins ago
add a comment |
Assuming the weights of the graph are distinct, the edge with the minimum weight will be present in all the minimum spanning trees.
– Gokul
1 hour ago
@Gokul minimum spanning tree? What?...
– Mr. Sigma.
34 mins ago
Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
28 mins ago
Assuming the weights of the graph are distinct, the edge with the minimum weight will be present in all the minimum spanning trees.
– Gokul
1 hour ago
Assuming the weights of the graph are distinct, the edge with the minimum weight will be present in all the minimum spanning trees.
– Gokul
1 hour ago
@Gokul minimum spanning tree? What?...
– Mr. Sigma.
34 mins ago
@Gokul minimum spanning tree? What?...
– Mr. Sigma.
34 mins ago
Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
28 mins ago
Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
28 mins ago
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
No, it's not true that any two spanning trees of a graph have common edges.
Consider the wheel graph:
You can make a spanning tree with edges "inside" the loop and another one from the outer loop.
add a comment |
up vote
2
down vote
No, consider the complete graph $K_4$:
It has the following edge-disjoint spanning trees:
1
Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
4 mins ago
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
No, it's not true that any two spanning trees of a graph have common edges.
Consider the wheel graph:
You can make a spanning tree with edges "inside" the loop and another one from the outer loop.
add a comment |
up vote
2
down vote
No, it's not true that any two spanning trees of a graph have common edges.
Consider the wheel graph:
You can make a spanning tree with edges "inside" the loop and another one from the outer loop.
add a comment |
up vote
2
down vote
up vote
2
down vote
No, it's not true that any two spanning trees of a graph have common edges.
Consider the wheel graph:
You can make a spanning tree with edges "inside" the loop and another one from the outer loop.
No, it's not true that any two spanning trees of a graph have common edges.
Consider the wheel graph:
You can make a spanning tree with edges "inside" the loop and another one from the outer loop.
answered 26 mins ago
Gokul
241110
241110
add a comment |
add a comment |
up vote
2
down vote
No, consider the complete graph $K_4$:
It has the following edge-disjoint spanning trees:
1
Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
4 mins ago
add a comment |
up vote
2
down vote
No, consider the complete graph $K_4$:
It has the following edge-disjoint spanning trees:
1
Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
4 mins ago
add a comment |
up vote
2
down vote
up vote
2
down vote
No, consider the complete graph $K_4$:
It has the following edge-disjoint spanning trees:
No, consider the complete graph $K_4$:
It has the following edge-disjoint spanning trees:
edited 22 mins ago
answered 28 mins ago
Bjørn Kjos-Hanssen
23417
23417
1
Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
4 mins ago
add a comment |
1
Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
4 mins ago
1
1
Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
4 mins ago
Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
4 mins ago
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f101038%2fdo-any-two-spanning-trees-of-a-simple-graph-always-have-some-common-edges%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Assuming the weights of the graph are distinct, the edge with the minimum weight will be present in all the minimum spanning trees.
– Gokul
1 hour ago
@Gokul minimum spanning tree? What?...
– Mr. Sigma.
34 mins ago
Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
28 mins ago