How many different spanning trees of $K_n setminus e$ are there?












5














I need to know how many different spanning trees of $K_n setminus e$ are there. $K_n setminus e$ is a graph created by removing one of the edges of a full graph $K_n$.



Well as we all know the number of spanning trees of a full graph is $n^{n-2}$. But graphs fulfill the deletion-contraction rule, meaning that $tau$ being the number of spanning trees fulfills the following equality.



$tau(K_n)-tau(K_n / e)=tau(K_n setminus e)$, where $K_n / e$ is a graph made by joining two vertices at the end of edge $e$ and connecting it to all neigbours of edges that lie on $e$. But $K_n / e$ is $K_{n-1}$, right? It has $n-1$ vertices and each an every one of them connects to each other. Therefore $tau(K_n setminus e)=n^{n-2}-(n-1)^{n-3}$, right?



Or does deletion contraction rule not apply to simple graphs?










share|cite|improve this question




















  • 1




    Contraction-Deletion doesn't apply here the way you want it to. In particular, the edge contraction of $K_{n+1}$ doesn't give $K_n$. Instead, there are $2$ edges incident on the contracted vertex. So while it's a valid formula, the resulting graph is not a simple complete graph and so Cayley's theore no longer applies.
    – EuYu
    Feb 7 '14 at 5:22












  • Why doesn't Cayley's formula apply here? A spanning tree of edge contracted $K_{n+1}$ only uses one of the double edges between the contracted vertex and all other ones, so we could form a bijection between such spanning tree and a spanning tree $K_n$. Does the fact which edge is used make such a difference? I thought that Cayley's formula only differentiated between which vertices are connected, and not which edges were used...
    – Arek Krawczyk
    Feb 7 '14 at 7:58












  • Distinguishing between which vertices are used is equivalent to distinguishing between which edges are used for a simple graph. Any two vertices uniquely determine an edge in that case. To see why multiple edges must be considered, try your argument on $K_3$. $K_3$ has three spanning trees. If you contract an edge without considering multiple edges, you get $K_2$ which has a single spanning tree. Then your formula says $K_3cdot e$ has two spanning trees, which is incorrect.
    – EuYu
    Feb 7 '14 at 16:04












  • Your notation is nonstandard. Normally $G/e$ is the contracted graph. Some people use $Gsetminus e$ for the graph with $e$ deleted, but since these notations are easy to mix up many people just use $G-e$ for that.
    – Especially Lime
    Feb 3 '17 at 6:47
















5














I need to know how many different spanning trees of $K_n setminus e$ are there. $K_n setminus e$ is a graph created by removing one of the edges of a full graph $K_n$.



Well as we all know the number of spanning trees of a full graph is $n^{n-2}$. But graphs fulfill the deletion-contraction rule, meaning that $tau$ being the number of spanning trees fulfills the following equality.



$tau(K_n)-tau(K_n / e)=tau(K_n setminus e)$, where $K_n / e$ is a graph made by joining two vertices at the end of edge $e$ and connecting it to all neigbours of edges that lie on $e$. But $K_n / e$ is $K_{n-1}$, right? It has $n-1$ vertices and each an every one of them connects to each other. Therefore $tau(K_n setminus e)=n^{n-2}-(n-1)^{n-3}$, right?



Or does deletion contraction rule not apply to simple graphs?










share|cite|improve this question




















  • 1




    Contraction-Deletion doesn't apply here the way you want it to. In particular, the edge contraction of $K_{n+1}$ doesn't give $K_n$. Instead, there are $2$ edges incident on the contracted vertex. So while it's a valid formula, the resulting graph is not a simple complete graph and so Cayley's theore no longer applies.
    – EuYu
    Feb 7 '14 at 5:22












  • Why doesn't Cayley's formula apply here? A spanning tree of edge contracted $K_{n+1}$ only uses one of the double edges between the contracted vertex and all other ones, so we could form a bijection between such spanning tree and a spanning tree $K_n$. Does the fact which edge is used make such a difference? I thought that Cayley's formula only differentiated between which vertices are connected, and not which edges were used...
    – Arek Krawczyk
    Feb 7 '14 at 7:58












  • Distinguishing between which vertices are used is equivalent to distinguishing between which edges are used for a simple graph. Any two vertices uniquely determine an edge in that case. To see why multiple edges must be considered, try your argument on $K_3$. $K_3$ has three spanning trees. If you contract an edge without considering multiple edges, you get $K_2$ which has a single spanning tree. Then your formula says $K_3cdot e$ has two spanning trees, which is incorrect.
    – EuYu
    Feb 7 '14 at 16:04












  • Your notation is nonstandard. Normally $G/e$ is the contracted graph. Some people use $Gsetminus e$ for the graph with $e$ deleted, but since these notations are easy to mix up many people just use $G-e$ for that.
    – Especially Lime
    Feb 3 '17 at 6:47














5












5








5


5





I need to know how many different spanning trees of $K_n setminus e$ are there. $K_n setminus e$ is a graph created by removing one of the edges of a full graph $K_n$.



Well as we all know the number of spanning trees of a full graph is $n^{n-2}$. But graphs fulfill the deletion-contraction rule, meaning that $tau$ being the number of spanning trees fulfills the following equality.



$tau(K_n)-tau(K_n / e)=tau(K_n setminus e)$, where $K_n / e$ is a graph made by joining two vertices at the end of edge $e$ and connecting it to all neigbours of edges that lie on $e$. But $K_n / e$ is $K_{n-1}$, right? It has $n-1$ vertices and each an every one of them connects to each other. Therefore $tau(K_n setminus e)=n^{n-2}-(n-1)^{n-3}$, right?



Or does deletion contraction rule not apply to simple graphs?










share|cite|improve this question















I need to know how many different spanning trees of $K_n setminus e$ are there. $K_n setminus e$ is a graph created by removing one of the edges of a full graph $K_n$.



Well as we all know the number of spanning trees of a full graph is $n^{n-2}$. But graphs fulfill the deletion-contraction rule, meaning that $tau$ being the number of spanning trees fulfills the following equality.



$tau(K_n)-tau(K_n / e)=tau(K_n setminus e)$, where $K_n / e$ is a graph made by joining two vertices at the end of edge $e$ and connecting it to all neigbours of edges that lie on $e$. But $K_n / e$ is $K_{n-1}$, right? It has $n-1$ vertices and each an every one of them connects to each other. Therefore $tau(K_n setminus e)=n^{n-2}-(n-1)^{n-3}$, right?



Or does deletion contraction rule not apply to simple graphs?







combinatorics graph-theory trees






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 26 at 16:59









Trevor Gunn

14.2k32046




14.2k32046










asked Feb 7 '14 at 5:05









Arek Krawczyk

1,10811020




1,10811020








  • 1




    Contraction-Deletion doesn't apply here the way you want it to. In particular, the edge contraction of $K_{n+1}$ doesn't give $K_n$. Instead, there are $2$ edges incident on the contracted vertex. So while it's a valid formula, the resulting graph is not a simple complete graph and so Cayley's theore no longer applies.
    – EuYu
    Feb 7 '14 at 5:22












  • Why doesn't Cayley's formula apply here? A spanning tree of edge contracted $K_{n+1}$ only uses one of the double edges between the contracted vertex and all other ones, so we could form a bijection between such spanning tree and a spanning tree $K_n$. Does the fact which edge is used make such a difference? I thought that Cayley's formula only differentiated between which vertices are connected, and not which edges were used...
    – Arek Krawczyk
    Feb 7 '14 at 7:58












  • Distinguishing between which vertices are used is equivalent to distinguishing between which edges are used for a simple graph. Any two vertices uniquely determine an edge in that case. To see why multiple edges must be considered, try your argument on $K_3$. $K_3$ has three spanning trees. If you contract an edge without considering multiple edges, you get $K_2$ which has a single spanning tree. Then your formula says $K_3cdot e$ has two spanning trees, which is incorrect.
    – EuYu
    Feb 7 '14 at 16:04












  • Your notation is nonstandard. Normally $G/e$ is the contracted graph. Some people use $Gsetminus e$ for the graph with $e$ deleted, but since these notations are easy to mix up many people just use $G-e$ for that.
    – Especially Lime
    Feb 3 '17 at 6:47














  • 1




    Contraction-Deletion doesn't apply here the way you want it to. In particular, the edge contraction of $K_{n+1}$ doesn't give $K_n$. Instead, there are $2$ edges incident on the contracted vertex. So while it's a valid formula, the resulting graph is not a simple complete graph and so Cayley's theore no longer applies.
    – EuYu
    Feb 7 '14 at 5:22












  • Why doesn't Cayley's formula apply here? A spanning tree of edge contracted $K_{n+1}$ only uses one of the double edges between the contracted vertex and all other ones, so we could form a bijection between such spanning tree and a spanning tree $K_n$. Does the fact which edge is used make such a difference? I thought that Cayley's formula only differentiated between which vertices are connected, and not which edges were used...
    – Arek Krawczyk
    Feb 7 '14 at 7:58












  • Distinguishing between which vertices are used is equivalent to distinguishing between which edges are used for a simple graph. Any two vertices uniquely determine an edge in that case. To see why multiple edges must be considered, try your argument on $K_3$. $K_3$ has three spanning trees. If you contract an edge without considering multiple edges, you get $K_2$ which has a single spanning tree. Then your formula says $K_3cdot e$ has two spanning trees, which is incorrect.
    – EuYu
    Feb 7 '14 at 16:04












  • Your notation is nonstandard. Normally $G/e$ is the contracted graph. Some people use $Gsetminus e$ for the graph with $e$ deleted, but since these notations are easy to mix up many people just use $G-e$ for that.
    – Especially Lime
    Feb 3 '17 at 6:47








1




1




Contraction-Deletion doesn't apply here the way you want it to. In particular, the edge contraction of $K_{n+1}$ doesn't give $K_n$. Instead, there are $2$ edges incident on the contracted vertex. So while it's a valid formula, the resulting graph is not a simple complete graph and so Cayley's theore no longer applies.
– EuYu
Feb 7 '14 at 5:22






Contraction-Deletion doesn't apply here the way you want it to. In particular, the edge contraction of $K_{n+1}$ doesn't give $K_n$. Instead, there are $2$ edges incident on the contracted vertex. So while it's a valid formula, the resulting graph is not a simple complete graph and so Cayley's theore no longer applies.
– EuYu
Feb 7 '14 at 5:22














Why doesn't Cayley's formula apply here? A spanning tree of edge contracted $K_{n+1}$ only uses one of the double edges between the contracted vertex and all other ones, so we could form a bijection between such spanning tree and a spanning tree $K_n$. Does the fact which edge is used make such a difference? I thought that Cayley's formula only differentiated between which vertices are connected, and not which edges were used...
– Arek Krawczyk
Feb 7 '14 at 7:58






Why doesn't Cayley's formula apply here? A spanning tree of edge contracted $K_{n+1}$ only uses one of the double edges between the contracted vertex and all other ones, so we could form a bijection between such spanning tree and a spanning tree $K_n$. Does the fact which edge is used make such a difference? I thought that Cayley's formula only differentiated between which vertices are connected, and not which edges were used...
– Arek Krawczyk
Feb 7 '14 at 7:58














Distinguishing between which vertices are used is equivalent to distinguishing between which edges are used for a simple graph. Any two vertices uniquely determine an edge in that case. To see why multiple edges must be considered, try your argument on $K_3$. $K_3$ has three spanning trees. If you contract an edge without considering multiple edges, you get $K_2$ which has a single spanning tree. Then your formula says $K_3cdot e$ has two spanning trees, which is incorrect.
– EuYu
Feb 7 '14 at 16:04






Distinguishing between which vertices are used is equivalent to distinguishing between which edges are used for a simple graph. Any two vertices uniquely determine an edge in that case. To see why multiple edges must be considered, try your argument on $K_3$. $K_3$ has three spanning trees. If you contract an edge without considering multiple edges, you get $K_2$ which has a single spanning tree. Then your formula says $K_3cdot e$ has two spanning trees, which is incorrect.
– EuYu
Feb 7 '14 at 16:04














Your notation is nonstandard. Normally $G/e$ is the contracted graph. Some people use $Gsetminus e$ for the graph with $e$ deleted, but since these notations are easy to mix up many people just use $G-e$ for that.
– Especially Lime
Feb 3 '17 at 6:47




Your notation is nonstandard. Normally $G/e$ is the contracted graph. Some people use $Gsetminus e$ for the graph with $e$ deleted, but since these notations are easy to mix up many people just use $G-e$ for that.
– Especially Lime
Feb 3 '17 at 6:47










3 Answers
3






active

oldest

votes


















8














We create a bipartite graph. In one part we have the $n^{n-2}$ labeled spanning trees of $K_n$, and in the other part we have the $binom{n}{2}$ edges in $K_n$, and we draw an edge between two vertices whenever a tree contains an edge. It'll looks something like the image below:



enter image description here



Trees have $n-1$ edges, so the degree of every tree vertex in the above graph is $n-1$. By symmetry, every edge in $K_n$ belongs to the same number of trees, say $d$, which is also the degree of any edge vertex in the above graph. Hence the number of edges in the above graph is $$n^{n-2} (n-1)=d binom{n}{2}$$ which implies that $$d=frac{n^{n-2} (n-1)}{binom{n}{2}}=2n^{n-3}.$$



The number of trees that contain a given edge is $d$, so the number of trees that don't contain that edge is $$n^{n-2}-d=n^{n-3}(n-2).$$ This is also the number of labeled spanning trees of $K_n setminus {e}$.






share|cite|improve this answer





























    6














    Your notation is confusing, but I think you want the number of spanning trees in the graph $K_n-e$, obtained by removing one edge from the complete graph $K_n$. In other words, you want the number of spanning trees in $K_n$ which do not contain a given edge $e$.



    Each spanning tree contains $n-1$ of the $binom n2$ edges of $K_n$, that is, the proportion $dfrac{n-1}{binom n2}=dfrac2n$ of all the edges. Equivalently, a given edge $e$ belongs to $dfrac2n$ of all the spanning trees, and is omitted by $dfrac{n-2}n$ of all the spanning trees. Since the total number of spanning trees is $n^{n-2}$, the number of spanning trees omitting $e$ is$$frac{n-2}ncdot n^{n-2}=(n-2)n^{n-3}.$$






    share|cite|improve this answer





























      2














      Another way to solve this is to use Prüfer Code (Wikipedia), a sequence of $n-2$ numbers each from $1$ to $n$ that uniquely identifies all $n^{n-2}$ spanning trees, where n is the number of vertices.



      Without the loss of generality (due to isomorphism), we can label the two vertices containing the edge that is deleted as "$n$" and "$n-1$".



      Since in the process of constructing Prufer code, we always remove the smallest labeled leaf vertices, $e$ will always be the last edge left. Therefore, the last removed leaf must be attached to either the vertex with label n, or n-1, making the last element of the generated Prüfer code n, or n-1.



      For all spanning trees, we have $n^{n-2}$ of them because in Prüfer code, there are $n$ choices each for the $n-2$ slots. Instead of having $n$ choices for the last element of the Prufer code, we have two. As a result, there are $2n^{n-3}$ spanning trees using edge e, and $(n-2)n^{n-3}$ spanning trees in $(G-e)$.






      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: "69"
        };
        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: true,
        noModals: true,
        showLowRepImageUploadWarning: true,
        reputationToPostImages: 10,
        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
        },
        noCode: true, onDemand: true,
        discardSelector: ".discard-answer"
        ,immediatelyShowMarkdownHelp:true
        });


        }
        });














        draft saved

        draft discarded


















        StackExchange.ready(
        function () {
        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f666997%2fhow-many-different-spanning-trees-of-k-n-setminus-e-are-there%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        3 Answers
        3






        active

        oldest

        votes








        3 Answers
        3






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        8














        We create a bipartite graph. In one part we have the $n^{n-2}$ labeled spanning trees of $K_n$, and in the other part we have the $binom{n}{2}$ edges in $K_n$, and we draw an edge between two vertices whenever a tree contains an edge. It'll looks something like the image below:



        enter image description here



        Trees have $n-1$ edges, so the degree of every tree vertex in the above graph is $n-1$. By symmetry, every edge in $K_n$ belongs to the same number of trees, say $d$, which is also the degree of any edge vertex in the above graph. Hence the number of edges in the above graph is $$n^{n-2} (n-1)=d binom{n}{2}$$ which implies that $$d=frac{n^{n-2} (n-1)}{binom{n}{2}}=2n^{n-3}.$$



        The number of trees that contain a given edge is $d$, so the number of trees that don't contain that edge is $$n^{n-2}-d=n^{n-3}(n-2).$$ This is also the number of labeled spanning trees of $K_n setminus {e}$.






        share|cite|improve this answer


























          8














          We create a bipartite graph. In one part we have the $n^{n-2}$ labeled spanning trees of $K_n$, and in the other part we have the $binom{n}{2}$ edges in $K_n$, and we draw an edge between two vertices whenever a tree contains an edge. It'll looks something like the image below:



          enter image description here



          Trees have $n-1$ edges, so the degree of every tree vertex in the above graph is $n-1$. By symmetry, every edge in $K_n$ belongs to the same number of trees, say $d$, which is also the degree of any edge vertex in the above graph. Hence the number of edges in the above graph is $$n^{n-2} (n-1)=d binom{n}{2}$$ which implies that $$d=frac{n^{n-2} (n-1)}{binom{n}{2}}=2n^{n-3}.$$



          The number of trees that contain a given edge is $d$, so the number of trees that don't contain that edge is $$n^{n-2}-d=n^{n-3}(n-2).$$ This is also the number of labeled spanning trees of $K_n setminus {e}$.






          share|cite|improve this answer
























            8












            8








            8






            We create a bipartite graph. In one part we have the $n^{n-2}$ labeled spanning trees of $K_n$, and in the other part we have the $binom{n}{2}$ edges in $K_n$, and we draw an edge between two vertices whenever a tree contains an edge. It'll looks something like the image below:



            enter image description here



            Trees have $n-1$ edges, so the degree of every tree vertex in the above graph is $n-1$. By symmetry, every edge in $K_n$ belongs to the same number of trees, say $d$, which is also the degree of any edge vertex in the above graph. Hence the number of edges in the above graph is $$n^{n-2} (n-1)=d binom{n}{2}$$ which implies that $$d=frac{n^{n-2} (n-1)}{binom{n}{2}}=2n^{n-3}.$$



            The number of trees that contain a given edge is $d$, so the number of trees that don't contain that edge is $$n^{n-2}-d=n^{n-3}(n-2).$$ This is also the number of labeled spanning trees of $K_n setminus {e}$.






            share|cite|improve this answer












            We create a bipartite graph. In one part we have the $n^{n-2}$ labeled spanning trees of $K_n$, and in the other part we have the $binom{n}{2}$ edges in $K_n$, and we draw an edge between two vertices whenever a tree contains an edge. It'll looks something like the image below:



            enter image description here



            Trees have $n-1$ edges, so the degree of every tree vertex in the above graph is $n-1$. By symmetry, every edge in $K_n$ belongs to the same number of trees, say $d$, which is also the degree of any edge vertex in the above graph. Hence the number of edges in the above graph is $$n^{n-2} (n-1)=d binom{n}{2}$$ which implies that $$d=frac{n^{n-2} (n-1)}{binom{n}{2}}=2n^{n-3}.$$



            The number of trees that contain a given edge is $d$, so the number of trees that don't contain that edge is $$n^{n-2}-d=n^{n-3}(n-2).$$ This is also the number of labeled spanning trees of $K_n setminus {e}$.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Feb 7 '14 at 5:23









            Rebecca J. Stones

            20.9k22781




            20.9k22781























                6














                Your notation is confusing, but I think you want the number of spanning trees in the graph $K_n-e$, obtained by removing one edge from the complete graph $K_n$. In other words, you want the number of spanning trees in $K_n$ which do not contain a given edge $e$.



                Each spanning tree contains $n-1$ of the $binom n2$ edges of $K_n$, that is, the proportion $dfrac{n-1}{binom n2}=dfrac2n$ of all the edges. Equivalently, a given edge $e$ belongs to $dfrac2n$ of all the spanning trees, and is omitted by $dfrac{n-2}n$ of all the spanning trees. Since the total number of spanning trees is $n^{n-2}$, the number of spanning trees omitting $e$ is$$frac{n-2}ncdot n^{n-2}=(n-2)n^{n-3}.$$






                share|cite|improve this answer


























                  6














                  Your notation is confusing, but I think you want the number of spanning trees in the graph $K_n-e$, obtained by removing one edge from the complete graph $K_n$. In other words, you want the number of spanning trees in $K_n$ which do not contain a given edge $e$.



                  Each spanning tree contains $n-1$ of the $binom n2$ edges of $K_n$, that is, the proportion $dfrac{n-1}{binom n2}=dfrac2n$ of all the edges. Equivalently, a given edge $e$ belongs to $dfrac2n$ of all the spanning trees, and is omitted by $dfrac{n-2}n$ of all the spanning trees. Since the total number of spanning trees is $n^{n-2}$, the number of spanning trees omitting $e$ is$$frac{n-2}ncdot n^{n-2}=(n-2)n^{n-3}.$$






                  share|cite|improve this answer
























                    6












                    6








                    6






                    Your notation is confusing, but I think you want the number of spanning trees in the graph $K_n-e$, obtained by removing one edge from the complete graph $K_n$. In other words, you want the number of spanning trees in $K_n$ which do not contain a given edge $e$.



                    Each spanning tree contains $n-1$ of the $binom n2$ edges of $K_n$, that is, the proportion $dfrac{n-1}{binom n2}=dfrac2n$ of all the edges. Equivalently, a given edge $e$ belongs to $dfrac2n$ of all the spanning trees, and is omitted by $dfrac{n-2}n$ of all the spanning trees. Since the total number of spanning trees is $n^{n-2}$, the number of spanning trees omitting $e$ is$$frac{n-2}ncdot n^{n-2}=(n-2)n^{n-3}.$$






                    share|cite|improve this answer












                    Your notation is confusing, but I think you want the number of spanning trees in the graph $K_n-e$, obtained by removing one edge from the complete graph $K_n$. In other words, you want the number of spanning trees in $K_n$ which do not contain a given edge $e$.



                    Each spanning tree contains $n-1$ of the $binom n2$ edges of $K_n$, that is, the proportion $dfrac{n-1}{binom n2}=dfrac2n$ of all the edges. Equivalently, a given edge $e$ belongs to $dfrac2n$ of all the spanning trees, and is omitted by $dfrac{n-2}n$ of all the spanning trees. Since the total number of spanning trees is $n^{n-2}$, the number of spanning trees omitting $e$ is$$frac{n-2}ncdot n^{n-2}=(n-2)n^{n-3}.$$







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Feb 7 '14 at 5:37









                    bof

                    50.1k457119




                    50.1k457119























                        2














                        Another way to solve this is to use Prüfer Code (Wikipedia), a sequence of $n-2$ numbers each from $1$ to $n$ that uniquely identifies all $n^{n-2}$ spanning trees, where n is the number of vertices.



                        Without the loss of generality (due to isomorphism), we can label the two vertices containing the edge that is deleted as "$n$" and "$n-1$".



                        Since in the process of constructing Prufer code, we always remove the smallest labeled leaf vertices, $e$ will always be the last edge left. Therefore, the last removed leaf must be attached to either the vertex with label n, or n-1, making the last element of the generated Prüfer code n, or n-1.



                        For all spanning trees, we have $n^{n-2}$ of them because in Prüfer code, there are $n$ choices each for the $n-2$ slots. Instead of having $n$ choices for the last element of the Prufer code, we have two. As a result, there are $2n^{n-3}$ spanning trees using edge e, and $(n-2)n^{n-3}$ spanning trees in $(G-e)$.






                        share|cite|improve this answer


























                          2














                          Another way to solve this is to use Prüfer Code (Wikipedia), a sequence of $n-2$ numbers each from $1$ to $n$ that uniquely identifies all $n^{n-2}$ spanning trees, where n is the number of vertices.



                          Without the loss of generality (due to isomorphism), we can label the two vertices containing the edge that is deleted as "$n$" and "$n-1$".



                          Since in the process of constructing Prufer code, we always remove the smallest labeled leaf vertices, $e$ will always be the last edge left. Therefore, the last removed leaf must be attached to either the vertex with label n, or n-1, making the last element of the generated Prüfer code n, or n-1.



                          For all spanning trees, we have $n^{n-2}$ of them because in Prüfer code, there are $n$ choices each for the $n-2$ slots. Instead of having $n$ choices for the last element of the Prufer code, we have two. As a result, there are $2n^{n-3}$ spanning trees using edge e, and $(n-2)n^{n-3}$ spanning trees in $(G-e)$.






                          share|cite|improve this answer
























                            2












                            2








                            2






                            Another way to solve this is to use Prüfer Code (Wikipedia), a sequence of $n-2$ numbers each from $1$ to $n$ that uniquely identifies all $n^{n-2}$ spanning trees, where n is the number of vertices.



                            Without the loss of generality (due to isomorphism), we can label the two vertices containing the edge that is deleted as "$n$" and "$n-1$".



                            Since in the process of constructing Prufer code, we always remove the smallest labeled leaf vertices, $e$ will always be the last edge left. Therefore, the last removed leaf must be attached to either the vertex with label n, or n-1, making the last element of the generated Prüfer code n, or n-1.



                            For all spanning trees, we have $n^{n-2}$ of them because in Prüfer code, there are $n$ choices each for the $n-2$ slots. Instead of having $n$ choices for the last element of the Prufer code, we have two. As a result, there are $2n^{n-3}$ spanning trees using edge e, and $(n-2)n^{n-3}$ spanning trees in $(G-e)$.






                            share|cite|improve this answer












                            Another way to solve this is to use Prüfer Code (Wikipedia), a sequence of $n-2$ numbers each from $1$ to $n$ that uniquely identifies all $n^{n-2}$ spanning trees, where n is the number of vertices.



                            Without the loss of generality (due to isomorphism), we can label the two vertices containing the edge that is deleted as "$n$" and "$n-1$".



                            Since in the process of constructing Prufer code, we always remove the smallest labeled leaf vertices, $e$ will always be the last edge left. Therefore, the last removed leaf must be attached to either the vertex with label n, or n-1, making the last element of the generated Prüfer code n, or n-1.



                            For all spanning trees, we have $n^{n-2}$ of them because in Prüfer code, there are $n$ choices each for the $n-2$ slots. Instead of having $n$ choices for the last element of the Prufer code, we have two. As a result, there are $2n^{n-3}$ spanning trees using edge e, and $(n-2)n^{n-3}$ spanning trees in $(G-e)$.







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered Feb 3 '17 at 6:39









                            waltyellow

                            212




                            212






























                                draft saved

                                draft discarded




















































                                Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f666997%2fhow-many-different-spanning-trees-of-k-n-setminus-e-are-there%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

                                Probability when a professor distributes a quiz and homework assignment to a class of n students.

                                Aardman Animations

                                Are they similar matrix