Number of spanning trees in $K_n$ that contain a fixed tree?
$begingroup$
Given a fixed tree $F$ with $f$ vertices in a complete graph $K_n$. What is the number of spanning trees of $K_n$ containing $F$ as a sub graph?
A comment suggests it is $n^{n-f-1}f$. But I am not sure why. Maybe it is related to Prufer code?
combinatorics graph-theory
asked Jan 10 at 18:40
ConnorConnor
928514
$endgroup$
add a comment |
$begingroup$
Given a fixed tree $F$ with $f$ vertices in a complete graph $K_n$. What is the number of spanning trees of $K_n$ containing $F$ as a sub graph?
A comment suggests it is $n^{n-f-1}f$. But I am not sure why. Maybe it is related to Prufer code?
combinatorics graph-theory
asked Jan 10 at 18:40
ConnorConnor
928514
$endgroup$
add a comment |
$begingroup$
Given a fixed tree $F$ with $f$ vertices in a complete graph $K_n$. What is the number of spanning trees of $K_n$ containing $F$ as a sub graph?
A comment suggests it is $n^{n-f-1}f$. But I am not sure why. Maybe it is related to Prufer code?
combinatorics graph-theory
asked Jan 10 at 18:40
ConnorConnor
928514
$endgroup$
Given a fixed tree $F$ with $f$ vertices in a complete graph $K_n$. What is the number of spanning trees of $K_n$ containing $F$ as a sub graph?
A comment suggests it is $n^{n-f-1}f$. But I am not sure why. Maybe it is related to Prufer code?
combinatorics graph-theory
combinatorics graph-theory
asked Jan 10 at 18:40
ConnorConnor
928514
asked Jan 10 at 18:40
ConnorConnor
928514
asked Jan 10 at 18:40
ConnorConnor
928514
asked Jan 10 at 18:40
ConnorConnor
928514
asked Jan 10 at 18:40
ConnorConnor
928514
928514
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Lemma. The number of labeled $n$-vertex trees in which a fixed vertex has degree $k$ is $binom {n-2}{k-1} (n-1)^{n-k-1}$.
Proof. The degree of the vertex is one more than the number of times its label shows up in the Prüfer code. If the degree is supposed to be $k$, it shows up $k-1$ times, so there are $binom {n-2}{k-1} (n-1)^{n-k-1}$ Prüfer codes like this: $binom{n-2}{k-1}$ ways to choose where the fixed vertex appears, and $n-1$ ways to choose each of the $(n-2)-(k-1) = n-k-1$ remaining values in the code.
We can choose a spanning tree of $K_n$ containing $F$ in two steps. First, contract the vertices of $F$ to one vertex $v_F$ and choose a spanning tree of the resulting $K_{n-f+1}$. Second, if $v_F$ has degree $k$, we can expand it in $f^k$ ways to the original tree; for each edge out of $v_F$, we must choose which vertex of $F$ it's incident on.
By the lemma, summing over all possibilities for $k$, we see that there are $$sum_{k=1}^{n-f} binom{n-f-1}{k-1} (n-f)^{n-f-k} f^k$$ such trees. If we factor out an $f$ from the $f^k$ term, the rest simplifies to $n^{n-f-1}$ by the binomial theorem.
answered Jan 10 at 19:04
Misha LavrovMisha Lavrov
47.2k657107
$endgroup$
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: "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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3069025%2fnumber-of-spanning-trees-in-k-n-that-contain-a-fixed-tree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Lemma. The number of labeled $n$-vertex trees in which a fixed vertex has degree $k$ is $binom {n-2}{k-1} (n-1)^{n-k-1}$.
Proof. The degree of the vertex is one more than the number of times its label shows up in the Prüfer code. If the degree is supposed to be $k$, it shows up $k-1$ times, so there are $binom {n-2}{k-1} (n-1)^{n-k-1}$ Prüfer codes like this: $binom{n-2}{k-1}$ ways to choose where the fixed vertex appears, and $n-1$ ways to choose each of the $(n-2)-(k-1) = n-k-1$ remaining values in the code.
We can choose a spanning tree of $K_n$ containing $F$ in two steps. First, contract the vertices of $F$ to one vertex $v_F$ and choose a spanning tree of the resulting $K_{n-f+1}$. Second, if $v_F$ has degree $k$, we can expand it in $f^k$ ways to the original tree; for each edge out of $v_F$, we must choose which vertex of $F$ it's incident on.
By the lemma, summing over all possibilities for $k$, we see that there are $$sum_{k=1}^{n-f} binom{n-f-1}{k-1} (n-f)^{n-f-k} f^k$$ such trees. If we factor out an $f$ from the $f^k$ term, the rest simplifies to $n^{n-f-1}$ by the binomial theorem.
answered Jan 10 at 19:04
Misha LavrovMisha Lavrov
47.2k657107
$endgroup$
add a comment |
$begingroup$
Lemma. The number of labeled $n$-vertex trees in which a fixed vertex has degree $k$ is $binom {n-2}{k-1} (n-1)^{n-k-1}$.
Proof. The degree of the vertex is one more than the number of times its label shows up in the Prüfer code. If the degree is supposed to be $k$, it shows up $k-1$ times, so there are $binom {n-2}{k-1} (n-1)^{n-k-1}$ Prüfer codes like this: $binom{n-2}{k-1}$ ways to choose where the fixed vertex appears, and $n-1$ ways to choose each of the $(n-2)-(k-1) = n-k-1$ remaining values in the code.
We can choose a spanning tree of $K_n$ containing $F$ in two steps. First, contract the vertices of $F$ to one vertex $v_F$ and choose a spanning tree of the resulting $K_{n-f+1}$. Second, if $v_F$ has degree $k$, we can expand it in $f^k$ ways to the original tree; for each edge out of $v_F$, we must choose which vertex of $F$ it's incident on.
By the lemma, summing over all possibilities for $k$, we see that there are $$sum_{k=1}^{n-f} binom{n-f-1}{k-1} (n-f)^{n-f-k} f^k$$ such trees. If we factor out an $f$ from the $f^k$ term, the rest simplifies to $n^{n-f-1}$ by the binomial theorem.
answered Jan 10 at 19:04
Misha LavrovMisha Lavrov
47.2k657107
$endgroup$
add a comment |
$begingroup$
Lemma. The number of labeled $n$-vertex trees in which a fixed vertex has degree $k$ is $binom {n-2}{k-1} (n-1)^{n-k-1}$.
Proof. The degree of the vertex is one more than the number of times its label shows up in the Prüfer code. If the degree is supposed to be $k$, it shows up $k-1$ times, so there are $binom {n-2}{k-1} (n-1)^{n-k-1}$ Prüfer codes like this: $binom{n-2}{k-1}$ ways to choose where the fixed vertex appears, and $n-1$ ways to choose each of the $(n-2)-(k-1) = n-k-1$ remaining values in the code.
We can choose a spanning tree of $K_n$ containing $F$ in two steps. First, contract the vertices of $F$ to one vertex $v_F$ and choose a spanning tree of the resulting $K_{n-f+1}$. Second, if $v_F$ has degree $k$, we can expand it in $f^k$ ways to the original tree; for each edge out of $v_F$, we must choose which vertex of $F$ it's incident on.
By the lemma, summing over all possibilities for $k$, we see that there are $$sum_{k=1}^{n-f} binom{n-f-1}{k-1} (n-f)^{n-f-k} f^k$$ such trees. If we factor out an $f$ from the $f^k$ term, the rest simplifies to $n^{n-f-1}$ by the binomial theorem.
answered Jan 10 at 19:04
Misha LavrovMisha Lavrov
47.2k657107
$endgroup$
Lemma. The number of labeled $n$-vertex trees in which a fixed vertex has degree $k$ is $binom {n-2}{k-1} (n-1)^{n-k-1}$.
Proof. The degree of the vertex is one more than the number of times its label shows up in the Prüfer code. If the degree is supposed to be $k$, it shows up $k-1$ times, so there are $binom {n-2}{k-1} (n-1)^{n-k-1}$ Prüfer codes like this: $binom{n-2}{k-1}$ ways to choose where the fixed vertex appears, and $n-1$ ways to choose each of the $(n-2)-(k-1) = n-k-1$ remaining values in the code.
We can choose a spanning tree of $K_n$ containing $F$ in two steps. First, contract the vertices of $F$ to one vertex $v_F$ and choose a spanning tree of the resulting $K_{n-f+1}$. Second, if $v_F$ has degree $k$, we can expand it in $f^k$ ways to the original tree; for each edge out of $v_F$, we must choose which vertex of $F$ it's incident on.
By the lemma, summing over all possibilities for $k$, we see that there are $$sum_{k=1}^{n-f} binom{n-f-1}{k-1} (n-f)^{n-f-k} f^k$$ such trees. If we factor out an $f$ from the $f^k$ term, the rest simplifies to $n^{n-f-1}$ by the binomial theorem.
answered Jan 10 at 19:04
Misha LavrovMisha Lavrov
47.2k657107
edited Jan 10 at 19:13
answered Jan 10 at 19:04
Misha LavrovMisha Lavrov
47.2k657107
answered Jan 10 at 19:04
Misha LavrovMisha Lavrov
47.2k657107
answered Jan 10 at 19:04
Misha LavrovMisha Lavrov
47.2k657107
47.2k657107
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3069025%2fnumber-of-spanning-trees-in-k-n-that-contain-a-fixed-tree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
