Do any two spanning trees of a simple graph always have some common edges?

up vote
2
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?

asked 4 hours ago

Mr. Sigma.

355116

Assuming the weights of the graph are distinct, the edge with the minimum weight will be present in all the minimum spanning trees.
– Gokul
4 hours ago

@Gokul minimum spanning tree? What?...
– Mr. Sigma.
3 hours ago

Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
3 hours ago

add a comment |

up vote
2
down vote

favorite

asked 4 hours ago

Mr. Sigma.

355116

Assuming the weights of the graph are distinct, the edge with the minimum weight will be present in all the minimum spanning trees.
– Gokul
4 hours ago

@Gokul minimum spanning tree? What?...
– Mr. Sigma.
3 hours ago

Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
3 hours ago

add a comment |

up vote
2
down vote

favorite

asked 4 hours ago

Mr. Sigma.

355116

graphs graph-theory spanning-trees

asked 4 hours ago

Mr. Sigma.

355116

asked 4 hours ago

Mr. Sigma.

355116

asked 4 hours ago

Mr. Sigma.

355116

asked 4 hours ago

Mr. Sigma.

355116

asked 4 hours ago

Mr. Sigma.

355116

Assuming the weights of the graph are distinct, the edge with the minimum weight will be present in all the minimum spanning trees.
– Gokul
4 hours ago

@Gokul minimum spanning tree? What?...
– Mr. Sigma.
3 hours ago

Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
3 hours 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
4 hours ago

@Gokul minimum spanning tree? What?...
– Mr. Sigma.
3 hours ago

Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
3 hours 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
4 hours ago

@Gokul minimum spanning tree? What?...
– Mr. Sigma.
3 hours ago

Oh, apologies. I read the title as whether minimum spanning tree have common edges.
– Gokul
3 hours ago

add a comment |

2 Answers
2

active

oldest

votes

up vote
6
down vote

accepted

EDIT: This is incorrect as pointed out in the comments. As the other answer says, a spanning tree for $K_4$ can be done without sharing edges.

No, it's not true that any two spanning trees of a graph have common edges.

Consider the wheel graph:

enter image description here

You can make a spanning tree with edges "inside" the loop and another one from the outer loop.

edited 1 hour ago

answered 3 hours ago

Gokul

296110

but the outer loop doesn't reach the center node
– amI
1 hour ago

You're right, I'll delete this answer as the other one suffices.
– Gokul
1 hour ago

1

You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
– boboquack
38 mins ago

add a comment |

up vote
5
down vote

No, consider the complete graph $K_4$:

It has the following edge-disjoint spanning trees:
enter image description here

edited 2 hours ago

answered 3 hours ago

Bjørn Kjos-Hanssen

27417

2

Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
2 hours ago

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

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

Name

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

up vote
6
down vote

accepted

EDIT: This is incorrect as pointed out in the comments. As the other answer says, a spanning tree for $K_4$ can be done without sharing edges.

No, it's not true that any two spanning trees of a graph have common edges.

Consider the wheel graph:

enter image description here

You can make a spanning tree with edges "inside" the loop and another one from the outer loop.

edited 1 hour ago

answered 3 hours ago

Gokul

296110

but the outer loop doesn't reach the center node
– amI
1 hour ago

You're right, I'll delete this answer as the other one suffices.
– Gokul
1 hour ago

1

You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
– boboquack
38 mins ago

add a comment |

up vote
6
down vote

accepted

EDIT: This is incorrect as pointed out in the comments. As the other answer says, a spanning tree for $K_4$ can be done without sharing edges.

No, it's not true that any two spanning trees of a graph have common edges.

Consider the wheel graph:

enter image description here

You can make a spanning tree with edges "inside" the loop and another one from the outer loop.

edited 1 hour ago

answered 3 hours ago

Gokul

296110

but the outer loop doesn't reach the center node
– amI
1 hour ago

You're right, I'll delete this answer as the other one suffices.
– Gokul
1 hour ago

1

You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
– boboquack
38 mins ago

add a comment |

up vote
6
down vote

accepted

EDIT: This is incorrect as pointed out in the comments. As the other answer says, a spanning tree for $K_4$ can be done without sharing edges.

No, it's not true that any two spanning trees of a graph have common edges.

Consider the wheel graph:

enter image description here

You can make a spanning tree with edges "inside" the loop and another one from the outer loop.

edited 1 hour ago

answered 3 hours ago

Gokul

296110

EDIT: This is incorrect as pointed out in the comments. As the other answer says, a spanning tree for $K_4$ can be done without sharing edges.

No, it's not true that any two spanning trees of a graph have common edges.

Consider the wheel graph:

enter image description here

You can make a spanning tree with edges "inside" the loop and another one from the outer loop.

edited 1 hour ago

answered 3 hours ago

Gokul

296110

edited 1 hour ago

answered 3 hours ago

Gokul

296110

answered 3 hours ago

Gokul

296110

answered 3 hours ago

Gokul

296110

but the outer loop doesn't reach the center node
– amI
1 hour ago

You're right, I'll delete this answer as the other one suffices.
– Gokul
1 hour ago

1

You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
– boboquack
38 mins ago

add a comment |

but the outer loop doesn't reach the center node
– amI
1 hour ago

You're right, I'll delete this answer as the other one suffices.
– Gokul
1 hour ago

1

You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
– boboquack
38 mins ago

but the outer loop doesn't reach the center node
– amI
1 hour ago

You're right, I'll delete this answer as the other one suffices.
– Gokul
1 hour ago

You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
– boboquack
38 mins ago

add a comment |

up vote
5
down vote

No, consider the complete graph $K_4$:

It has the following edge-disjoint spanning trees:
enter image description here

edited 2 hours ago

answered 3 hours ago

Bjørn Kjos-Hanssen

27417

2

Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
2 hours ago

add a comment |

up vote
5
down vote

No, consider the complete graph $K_4$:

It has the following edge-disjoint spanning trees:
enter image description here

edited 2 hours ago

answered 3 hours ago

Bjørn Kjos-Hanssen

27417

2

Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
2 hours ago

add a comment |

up vote
5
down vote

No, consider the complete graph $K_4$:

It has the following edge-disjoint spanning trees:
enter image description here

edited 2 hours ago

answered 3 hours ago

Bjørn Kjos-Hanssen

27417

No, consider the complete graph $K_4$:

It has the following edge-disjoint spanning trees:
enter image description here

edited 2 hours ago

answered 3 hours ago

Bjørn Kjos-Hanssen

27417

edited 2 hours ago

answered 3 hours ago

Bjørn Kjos-Hanssen

27417

answered 3 hours ago

Bjørn Kjos-Hanssen

27417

answered 3 hours ago

Bjørn Kjos-Hanssen

27417

2

Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
2 hours ago

add a comment |

2

Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
2 hours ago

Oh! Elegant. Why I couldn't come upon this solution. ':O.
– Mr. Sigma.
2 hours ago

add a comment |

draft saved

draft discarded

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.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Vrftsjtryk