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












21














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?










share|cite|improve this question



























    21














    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?










    share|cite|improve this question

























      21












      21








      21


      2





      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?










      share|cite|improve this question













      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






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Dec 5 at 2:59









      Mr. Sigma.

      544322




      544322






















          5 Answers
          5






          active

          oldest

          votes


















          43














          No, consider the complete graph $K_4$:



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






          share|cite|improve this answer



















          • 2




            You can make each of the trees planar by taking one to be $N$-shaped and the other $Z$-shaped. You can make the whole thing planar by drawing the edge from the upper right vertex to the lower left vertex as a curve going outside the square.
            – Acccumulation
            Dec 5 at 20:29










          • @kelalaka We don't need a complete graph, no (imagine doing this same sort of thing on $K_5$ -- unless I've missed my guess, you have a few unused edges that can be removed, making it no longer complete (because each vertex needs 2-4 traversed edges connected to it, and each vertex in $K_5$ has 5 edges available, so each vertex is attached to at least one unused edge)). $K_4$ is probably just the best example -- it's well known, easy to visualize (comparatively few edges), and has very simple spanning trees.
            – Nic Hartley
            Dec 6 at 6:40





















          14














          For the more interested readers, there are some research on decomposition of graph into edge-disjoint spanning trees.



          For example, the classical papers On the Problem of Decomposing a Graph into $n$ Connected Factors by W. T. Tutte and Edge-disjoint spanning trees of finite graphs by C. St.J. A. Nash-Williams provides a characterization of graphs that contains $k$ pairwise edge-disjoint spanning trees.



          For example, the paper Bi-cyclic decompositions of complete graphs into spanning trees by Dalibor Froncek shows how to decompose complete graphs $K_{4k+2}$ into isomorphic ${2k+1}$ spanning trees.



          For example, the paper Factorizations of Complete Graphs into Spanning Trees with All Possible Maximum Degrees by Petr Kovář and Michael Kubesa shows how to factorize $K_{2n}$ to spanning trees with a given maximum degree.



          You can search for more. For example, a Google search for decomposition of graph into spanning trees.






          share|cite|improve this answer





























            9














            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.






            share|cite|improve this answer



















            • 2




              but the outer loop doesn't reach the center node
              – amI
              Dec 5 at 6:21










            • You're right, I'll delete this answer as the other one suffices.
              – Gokul
              Dec 5 at 6:27






            • 10




              You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
              – boboquack
              Dec 5 at 6:56










            • Yes. Actually I had seen that way only. @boboquack
              – Mr. Sigma.
              Dec 5 at 8:09





















            3














            After observing the graphs presented by @Bjorn and @Gokul, I arrive at the conclusion that every complete graph $K_n$ with $ngeq4$ has at least two spanning trees with disjoint edges.
            enter image description here



            The graph given in the pic, which is wheel, has clearly two spanning trees with disjoint edges. In fact, every wheel will have exactly $2$ spanning trees with disjointed edges because one is complement graph of another.



            Now, If we look at the solution of @Bjorn carefully, we find that his graph & spanning trees are homomorphic to the graphs shown in the pic. In fact, every complete graph $K_n$ with $ngeq4$ has wheel as its subgraph, so it directly follows that every complete complete graph with $ngeq4$ has at least 2 (or exactly $2$?) spanning trees with disjoint edges.



            P.S:
            This observation gives birth to $2$ more interesting question.




            1. Is there any complete graph with more than $2$ spanning trees with disjoint edges? Or it will always have exactly $2$ spanning trees with disjoint edges.

            2. Is there any graph other than wheel or wheel as its subgraph having spanning trees with disjointed edges?






            share|cite|improve this answer





















            • These questions and beyond have been answered in the papers I cited. If you are interested, you can take a look.
              – Apass.Jack
              Dec 6 at 5:33












            • Thanks @Apass.Jack I have seen your answer. Will look at it.
              – Mr. Sigma.
              Dec 6 at 5:35



















            1














            For $K_{2k}$, I believe that



            $$G_1 = { (v_{2i},v_{2i+1} ),(v_{2i},v_{2i+2}),dots,(v_{2k-2},v_{2k-1})},$$



            $$G_2 = { (v_{2i+1},v_{2i+2}),(v_{2i},v_{2i}),dots(v_{2(k-1)},v_{2(k-1)})}$$



            for $0leq i < k$ are counterexamples. That is, for the first graph, take the vertices with even indices and connect them to the next vertex, and for all but the last even vertex, connect it to the vertex after that as well. For the second graph, do this with odd vertices.



            And inductively, once we have a counterexample for $n$ vertices, it's easy to construct a counterexample with $n+1$ vertices by connecting the new vertex with one edge for one graph, and with another edge for the other.






            share|cite|improve this answer























              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',
              autoActivateHeartbeat: false,
              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


















              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

























              5 Answers
              5






              active

              oldest

              votes








              5 Answers
              5






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              43














              No, consider the complete graph $K_4$:



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






              share|cite|improve this answer



















              • 2




                You can make each of the trees planar by taking one to be $N$-shaped and the other $Z$-shaped. You can make the whole thing planar by drawing the edge from the upper right vertex to the lower left vertex as a curve going outside the square.
                – Acccumulation
                Dec 5 at 20:29










              • @kelalaka We don't need a complete graph, no (imagine doing this same sort of thing on $K_5$ -- unless I've missed my guess, you have a few unused edges that can be removed, making it no longer complete (because each vertex needs 2-4 traversed edges connected to it, and each vertex in $K_5$ has 5 edges available, so each vertex is attached to at least one unused edge)). $K_4$ is probably just the best example -- it's well known, easy to visualize (comparatively few edges), and has very simple spanning trees.
                – Nic Hartley
                Dec 6 at 6:40


















              43














              No, consider the complete graph $K_4$:



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






              share|cite|improve this answer



















              • 2




                You can make each of the trees planar by taking one to be $N$-shaped and the other $Z$-shaped. You can make the whole thing planar by drawing the edge from the upper right vertex to the lower left vertex as a curve going outside the square.
                – Acccumulation
                Dec 5 at 20:29










              • @kelalaka We don't need a complete graph, no (imagine doing this same sort of thing on $K_5$ -- unless I've missed my guess, you have a few unused edges that can be removed, making it no longer complete (because each vertex needs 2-4 traversed edges connected to it, and each vertex in $K_5$ has 5 edges available, so each vertex is attached to at least one unused edge)). $K_4$ is probably just the best example -- it's well known, easy to visualize (comparatively few edges), and has very simple spanning trees.
                – Nic Hartley
                Dec 6 at 6:40
















              43












              43








              43






              No, consider the complete graph $K_4$:



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






              share|cite|improve this answer














              No, consider the complete graph $K_4$:



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







              share|cite|improve this answer














              share|cite|improve this answer



              share|cite|improve this answer








              edited Dec 5 at 4:35

























              answered Dec 5 at 4:30









              Bjørn Kjos-Hanssen

              594511




              594511








              • 2




                You can make each of the trees planar by taking one to be $N$-shaped and the other $Z$-shaped. You can make the whole thing planar by drawing the edge from the upper right vertex to the lower left vertex as a curve going outside the square.
                – Acccumulation
                Dec 5 at 20:29










              • @kelalaka We don't need a complete graph, no (imagine doing this same sort of thing on $K_5$ -- unless I've missed my guess, you have a few unused edges that can be removed, making it no longer complete (because each vertex needs 2-4 traversed edges connected to it, and each vertex in $K_5$ has 5 edges available, so each vertex is attached to at least one unused edge)). $K_4$ is probably just the best example -- it's well known, easy to visualize (comparatively few edges), and has very simple spanning trees.
                – Nic Hartley
                Dec 6 at 6:40
















              • 2




                You can make each of the trees planar by taking one to be $N$-shaped and the other $Z$-shaped. You can make the whole thing planar by drawing the edge from the upper right vertex to the lower left vertex as a curve going outside the square.
                – Acccumulation
                Dec 5 at 20:29










              • @kelalaka We don't need a complete graph, no (imagine doing this same sort of thing on $K_5$ -- unless I've missed my guess, you have a few unused edges that can be removed, making it no longer complete (because each vertex needs 2-4 traversed edges connected to it, and each vertex in $K_5$ has 5 edges available, so each vertex is attached to at least one unused edge)). $K_4$ is probably just the best example -- it's well known, easy to visualize (comparatively few edges), and has very simple spanning trees.
                – Nic Hartley
                Dec 6 at 6:40










              2




              2




              You can make each of the trees planar by taking one to be $N$-shaped and the other $Z$-shaped. You can make the whole thing planar by drawing the edge from the upper right vertex to the lower left vertex as a curve going outside the square.
              – Acccumulation
              Dec 5 at 20:29




              You can make each of the trees planar by taking one to be $N$-shaped and the other $Z$-shaped. You can make the whole thing planar by drawing the edge from the upper right vertex to the lower left vertex as a curve going outside the square.
              – Acccumulation
              Dec 5 at 20:29












              @kelalaka We don't need a complete graph, no (imagine doing this same sort of thing on $K_5$ -- unless I've missed my guess, you have a few unused edges that can be removed, making it no longer complete (because each vertex needs 2-4 traversed edges connected to it, and each vertex in $K_5$ has 5 edges available, so each vertex is attached to at least one unused edge)). $K_4$ is probably just the best example -- it's well known, easy to visualize (comparatively few edges), and has very simple spanning trees.
              – Nic Hartley
              Dec 6 at 6:40






              @kelalaka We don't need a complete graph, no (imagine doing this same sort of thing on $K_5$ -- unless I've missed my guess, you have a few unused edges that can be removed, making it no longer complete (because each vertex needs 2-4 traversed edges connected to it, and each vertex in $K_5$ has 5 edges available, so each vertex is attached to at least one unused edge)). $K_4$ is probably just the best example -- it's well known, easy to visualize (comparatively few edges), and has very simple spanning trees.
              – Nic Hartley
              Dec 6 at 6:40













              14














              For the more interested readers, there are some research on decomposition of graph into edge-disjoint spanning trees.



              For example, the classical papers On the Problem of Decomposing a Graph into $n$ Connected Factors by W. T. Tutte and Edge-disjoint spanning trees of finite graphs by C. St.J. A. Nash-Williams provides a characterization of graphs that contains $k$ pairwise edge-disjoint spanning trees.



              For example, the paper Bi-cyclic decompositions of complete graphs into spanning trees by Dalibor Froncek shows how to decompose complete graphs $K_{4k+2}$ into isomorphic ${2k+1}$ spanning trees.



              For example, the paper Factorizations of Complete Graphs into Spanning Trees with All Possible Maximum Degrees by Petr Kovář and Michael Kubesa shows how to factorize $K_{2n}$ to spanning trees with a given maximum degree.



              You can search for more. For example, a Google search for decomposition of graph into spanning trees.






              share|cite|improve this answer


























                14














                For the more interested readers, there are some research on decomposition of graph into edge-disjoint spanning trees.



                For example, the classical papers On the Problem of Decomposing a Graph into $n$ Connected Factors by W. T. Tutte and Edge-disjoint spanning trees of finite graphs by C. St.J. A. Nash-Williams provides a characterization of graphs that contains $k$ pairwise edge-disjoint spanning trees.



                For example, the paper Bi-cyclic decompositions of complete graphs into spanning trees by Dalibor Froncek shows how to decompose complete graphs $K_{4k+2}$ into isomorphic ${2k+1}$ spanning trees.



                For example, the paper Factorizations of Complete Graphs into Spanning Trees with All Possible Maximum Degrees by Petr Kovář and Michael Kubesa shows how to factorize $K_{2n}$ to spanning trees with a given maximum degree.



                You can search for more. For example, a Google search for decomposition of graph into spanning trees.






                share|cite|improve this answer
























                  14












                  14








                  14






                  For the more interested readers, there are some research on decomposition of graph into edge-disjoint spanning trees.



                  For example, the classical papers On the Problem of Decomposing a Graph into $n$ Connected Factors by W. T. Tutte and Edge-disjoint spanning trees of finite graphs by C. St.J. A. Nash-Williams provides a characterization of graphs that contains $k$ pairwise edge-disjoint spanning trees.



                  For example, the paper Bi-cyclic decompositions of complete graphs into spanning trees by Dalibor Froncek shows how to decompose complete graphs $K_{4k+2}$ into isomorphic ${2k+1}$ spanning trees.



                  For example, the paper Factorizations of Complete Graphs into Spanning Trees with All Possible Maximum Degrees by Petr Kovář and Michael Kubesa shows how to factorize $K_{2n}$ to spanning trees with a given maximum degree.



                  You can search for more. For example, a Google search for decomposition of graph into spanning trees.






                  share|cite|improve this answer












                  For the more interested readers, there are some research on decomposition of graph into edge-disjoint spanning trees.



                  For example, the classical papers On the Problem of Decomposing a Graph into $n$ Connected Factors by W. T. Tutte and Edge-disjoint spanning trees of finite graphs by C. St.J. A. Nash-Williams provides a characterization of graphs that contains $k$ pairwise edge-disjoint spanning trees.



                  For example, the paper Bi-cyclic decompositions of complete graphs into spanning trees by Dalibor Froncek shows how to decompose complete graphs $K_{4k+2}$ into isomorphic ${2k+1}$ spanning trees.



                  For example, the paper Factorizations of Complete Graphs into Spanning Trees with All Possible Maximum Degrees by Petr Kovář and Michael Kubesa shows how to factorize $K_{2n}$ to spanning trees with a given maximum degree.



                  You can search for more. For example, a Google search for decomposition of graph into spanning trees.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Dec 5 at 9:56









                  Apass.Jack

                  6,4151532




                  6,4151532























                      9














                      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.






                      share|cite|improve this answer



















                      • 2




                        but the outer loop doesn't reach the center node
                        – amI
                        Dec 5 at 6:21










                      • You're right, I'll delete this answer as the other one suffices.
                        – Gokul
                        Dec 5 at 6:27






                      • 10




                        You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
                        – boboquack
                        Dec 5 at 6:56










                      • Yes. Actually I had seen that way only. @boboquack
                        – Mr. Sigma.
                        Dec 5 at 8:09


















                      9














                      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.






                      share|cite|improve this answer



















                      • 2




                        but the outer loop doesn't reach the center node
                        – amI
                        Dec 5 at 6:21










                      • You're right, I'll delete this answer as the other one suffices.
                        – Gokul
                        Dec 5 at 6:27






                      • 10




                        You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
                        – boboquack
                        Dec 5 at 6:56










                      • Yes. Actually I had seen that way only. @boboquack
                        – Mr. Sigma.
                        Dec 5 at 8:09
















                      9












                      9








                      9






                      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.






                      share|cite|improve this answer














                      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.







                      share|cite|improve this answer














                      share|cite|improve this answer



                      share|cite|improve this answer








                      edited Dec 5 at 6:28

























                      answered Dec 5 at 4:32









                      Gokul

                      354111




                      354111








                      • 2




                        but the outer loop doesn't reach the center node
                        – amI
                        Dec 5 at 6:21










                      • You're right, I'll delete this answer as the other one suffices.
                        – Gokul
                        Dec 5 at 6:27






                      • 10




                        You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
                        – boboquack
                        Dec 5 at 6:56










                      • Yes. Actually I had seen that way only. @boboquack
                        – Mr. Sigma.
                        Dec 5 at 8:09
















                      • 2




                        but the outer loop doesn't reach the center node
                        – amI
                        Dec 5 at 6:21










                      • You're right, I'll delete this answer as the other one suffices.
                        – Gokul
                        Dec 5 at 6:27






                      • 10




                        You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
                        – boboquack
                        Dec 5 at 6:56










                      • Yes. Actually I had seen that way only. @boboquack
                        – Mr. Sigma.
                        Dec 5 at 8:09










                      2




                      2




                      but the outer loop doesn't reach the center node
                      – amI
                      Dec 5 at 6:21




                      but the outer loop doesn't reach the center node
                      – amI
                      Dec 5 at 6:21












                      You're right, I'll delete this answer as the other one suffices.
                      – Gokul
                      Dec 5 at 6:27




                      You're right, I'll delete this answer as the other one suffices.
                      – Gokul
                      Dec 5 at 6:27




                      10




                      10




                      You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
                      – boboquack
                      Dec 5 at 6:56




                      You can modify this by taking the out loop minus some "chord" plus some "radius" and its complement.
                      – boboquack
                      Dec 5 at 6:56












                      Yes. Actually I had seen that way only. @boboquack
                      – Mr. Sigma.
                      Dec 5 at 8:09






                      Yes. Actually I had seen that way only. @boboquack
                      – Mr. Sigma.
                      Dec 5 at 8:09













                      3














                      After observing the graphs presented by @Bjorn and @Gokul, I arrive at the conclusion that every complete graph $K_n$ with $ngeq4$ has at least two spanning trees with disjoint edges.
                      enter image description here



                      The graph given in the pic, which is wheel, has clearly two spanning trees with disjoint edges. In fact, every wheel will have exactly $2$ spanning trees with disjointed edges because one is complement graph of another.



                      Now, If we look at the solution of @Bjorn carefully, we find that his graph & spanning trees are homomorphic to the graphs shown in the pic. In fact, every complete graph $K_n$ with $ngeq4$ has wheel as its subgraph, so it directly follows that every complete complete graph with $ngeq4$ has at least 2 (or exactly $2$?) spanning trees with disjoint edges.



                      P.S:
                      This observation gives birth to $2$ more interesting question.




                      1. Is there any complete graph with more than $2$ spanning trees with disjoint edges? Or it will always have exactly $2$ spanning trees with disjoint edges.

                      2. Is there any graph other than wheel or wheel as its subgraph having spanning trees with disjointed edges?






                      share|cite|improve this answer





















                      • These questions and beyond have been answered in the papers I cited. If you are interested, you can take a look.
                        – Apass.Jack
                        Dec 6 at 5:33












                      • Thanks @Apass.Jack I have seen your answer. Will look at it.
                        – Mr. Sigma.
                        Dec 6 at 5:35
















                      3














                      After observing the graphs presented by @Bjorn and @Gokul, I arrive at the conclusion that every complete graph $K_n$ with $ngeq4$ has at least two spanning trees with disjoint edges.
                      enter image description here



                      The graph given in the pic, which is wheel, has clearly two spanning trees with disjoint edges. In fact, every wheel will have exactly $2$ spanning trees with disjointed edges because one is complement graph of another.



                      Now, If we look at the solution of @Bjorn carefully, we find that his graph & spanning trees are homomorphic to the graphs shown in the pic. In fact, every complete graph $K_n$ with $ngeq4$ has wheel as its subgraph, so it directly follows that every complete complete graph with $ngeq4$ has at least 2 (or exactly $2$?) spanning trees with disjoint edges.



                      P.S:
                      This observation gives birth to $2$ more interesting question.




                      1. Is there any complete graph with more than $2$ spanning trees with disjoint edges? Or it will always have exactly $2$ spanning trees with disjoint edges.

                      2. Is there any graph other than wheel or wheel as its subgraph having spanning trees with disjointed edges?






                      share|cite|improve this answer





















                      • These questions and beyond have been answered in the papers I cited. If you are interested, you can take a look.
                        – Apass.Jack
                        Dec 6 at 5:33












                      • Thanks @Apass.Jack I have seen your answer. Will look at it.
                        – Mr. Sigma.
                        Dec 6 at 5:35














                      3












                      3








                      3






                      After observing the graphs presented by @Bjorn and @Gokul, I arrive at the conclusion that every complete graph $K_n$ with $ngeq4$ has at least two spanning trees with disjoint edges.
                      enter image description here



                      The graph given in the pic, which is wheel, has clearly two spanning trees with disjoint edges. In fact, every wheel will have exactly $2$ spanning trees with disjointed edges because one is complement graph of another.



                      Now, If we look at the solution of @Bjorn carefully, we find that his graph & spanning trees are homomorphic to the graphs shown in the pic. In fact, every complete graph $K_n$ with $ngeq4$ has wheel as its subgraph, so it directly follows that every complete complete graph with $ngeq4$ has at least 2 (or exactly $2$?) spanning trees with disjoint edges.



                      P.S:
                      This observation gives birth to $2$ more interesting question.




                      1. Is there any complete graph with more than $2$ spanning trees with disjoint edges? Or it will always have exactly $2$ spanning trees with disjoint edges.

                      2. Is there any graph other than wheel or wheel as its subgraph having spanning trees with disjointed edges?






                      share|cite|improve this answer












                      After observing the graphs presented by @Bjorn and @Gokul, I arrive at the conclusion that every complete graph $K_n$ with $ngeq4$ has at least two spanning trees with disjoint edges.
                      enter image description here



                      The graph given in the pic, which is wheel, has clearly two spanning trees with disjoint edges. In fact, every wheel will have exactly $2$ spanning trees with disjointed edges because one is complement graph of another.



                      Now, If we look at the solution of @Bjorn carefully, we find that his graph & spanning trees are homomorphic to the graphs shown in the pic. In fact, every complete graph $K_n$ with $ngeq4$ has wheel as its subgraph, so it directly follows that every complete complete graph with $ngeq4$ has at least 2 (or exactly $2$?) spanning trees with disjoint edges.



                      P.S:
                      This observation gives birth to $2$ more interesting question.




                      1. Is there any complete graph with more than $2$ spanning trees with disjoint edges? Or it will always have exactly $2$ spanning trees with disjoint edges.

                      2. Is there any graph other than wheel or wheel as its subgraph having spanning trees with disjointed edges?







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Dec 6 at 5:04









                      Mr. Sigma.

                      544322




                      544322












                      • These questions and beyond have been answered in the papers I cited. If you are interested, you can take a look.
                        – Apass.Jack
                        Dec 6 at 5:33












                      • Thanks @Apass.Jack I have seen your answer. Will look at it.
                        – Mr. Sigma.
                        Dec 6 at 5:35


















                      • These questions and beyond have been answered in the papers I cited. If you are interested, you can take a look.
                        – Apass.Jack
                        Dec 6 at 5:33












                      • Thanks @Apass.Jack I have seen your answer. Will look at it.
                        – Mr. Sigma.
                        Dec 6 at 5:35
















                      These questions and beyond have been answered in the papers I cited. If you are interested, you can take a look.
                      – Apass.Jack
                      Dec 6 at 5:33






                      These questions and beyond have been answered in the papers I cited. If you are interested, you can take a look.
                      – Apass.Jack
                      Dec 6 at 5:33














                      Thanks @Apass.Jack I have seen your answer. Will look at it.
                      – Mr. Sigma.
                      Dec 6 at 5:35




                      Thanks @Apass.Jack I have seen your answer. Will look at it.
                      – Mr. Sigma.
                      Dec 6 at 5:35











                      1














                      For $K_{2k}$, I believe that



                      $$G_1 = { (v_{2i},v_{2i+1} ),(v_{2i},v_{2i+2}),dots,(v_{2k-2},v_{2k-1})},$$



                      $$G_2 = { (v_{2i+1},v_{2i+2}),(v_{2i},v_{2i}),dots(v_{2(k-1)},v_{2(k-1)})}$$



                      for $0leq i < k$ are counterexamples. That is, for the first graph, take the vertices with even indices and connect them to the next vertex, and for all but the last even vertex, connect it to the vertex after that as well. For the second graph, do this with odd vertices.



                      And inductively, once we have a counterexample for $n$ vertices, it's easy to construct a counterexample with $n+1$ vertices by connecting the new vertex with one edge for one graph, and with another edge for the other.






                      share|cite|improve this answer




























                        1














                        For $K_{2k}$, I believe that



                        $$G_1 = { (v_{2i},v_{2i+1} ),(v_{2i},v_{2i+2}),dots,(v_{2k-2},v_{2k-1})},$$



                        $$G_2 = { (v_{2i+1},v_{2i+2}),(v_{2i},v_{2i}),dots(v_{2(k-1)},v_{2(k-1)})}$$



                        for $0leq i < k$ are counterexamples. That is, for the first graph, take the vertices with even indices and connect them to the next vertex, and for all but the last even vertex, connect it to the vertex after that as well. For the second graph, do this with odd vertices.



                        And inductively, once we have a counterexample for $n$ vertices, it's easy to construct a counterexample with $n+1$ vertices by connecting the new vertex with one edge for one graph, and with another edge for the other.






                        share|cite|improve this answer


























                          1












                          1








                          1






                          For $K_{2k}$, I believe that



                          $$G_1 = { (v_{2i},v_{2i+1} ),(v_{2i},v_{2i+2}),dots,(v_{2k-2},v_{2k-1})},$$



                          $$G_2 = { (v_{2i+1},v_{2i+2}),(v_{2i},v_{2i}),dots(v_{2(k-1)},v_{2(k-1)})}$$



                          for $0leq i < k$ are counterexamples. That is, for the first graph, take the vertices with even indices and connect them to the next vertex, and for all but the last even vertex, connect it to the vertex after that as well. For the second graph, do this with odd vertices.



                          And inductively, once we have a counterexample for $n$ vertices, it's easy to construct a counterexample with $n+1$ vertices by connecting the new vertex with one edge for one graph, and with another edge for the other.






                          share|cite|improve this answer














                          For $K_{2k}$, I believe that



                          $$G_1 = { (v_{2i},v_{2i+1} ),(v_{2i},v_{2i+2}),dots,(v_{2k-2},v_{2k-1})},$$



                          $$G_2 = { (v_{2i+1},v_{2i+2}),(v_{2i},v_{2i}),dots(v_{2(k-1)},v_{2(k-1)})}$$



                          for $0leq i < k$ are counterexamples. That is, for the first graph, take the vertices with even indices and connect them to the next vertex, and for all but the last even vertex, connect it to the vertex after that as well. For the second graph, do this with odd vertices.



                          And inductively, once we have a counterexample for $n$ vertices, it's easy to construct a counterexample with $n+1$ vertices by connecting the new vertex with one edge for one graph, and with another edge for the other.







                          share|cite|improve this answer














                          share|cite|improve this answer



                          share|cite|improve this answer








                          edited Dec 7 at 14:40









                          David Richerby

                          65.7k15100190




                          65.7k15100190










                          answered Dec 5 at 20:13









                          Acccumulation

                          1194




                          1194






























                              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














                              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





















































                              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







                              Popular posts from this blog

                              Ellipse (mathématiques)

                              Quarter-circle Tiles

                              Mont Emei