The number of Hamiltonian cycles in the complete bipartite graphCounting Hamiltonian cycles in a...
Hackerrank All Women's Codesprint 2019: Name the Product
PTIJ: Which Dr. Seuss books should one obtain?
Why are there no stars visible in cislunar space?
How to test the sharpness of a knife?
When should a starting writer get his own webpage?
How to balance a monster modification (zombie)?
Homology of the fiber
Unfrosted light bulb
Emojional cryptic crossword
What is the reasoning behind standardization (dividing by standard deviation)?
PTIJ: At the Passover Seder, is one allowed to speak more than once during Maggid?
Exposing a company lying about themselves in a tightly knit industry: Is my career at risk on the long run?
Is xar preinstalled on macOS?
Does the Shadow Magic sorcerer's Eyes of the Dark feature work on all Darkness spells or just his/her own?
When did hardware antialiasing start being available?
Would this string work as string?
Turning a hard to access nut?
What is the difference between something being completely legal and being completely decriminalized?
Why is indicated airspeed rather than ground speed used during the takeoff roll?
Animating wave motion in water
What is it called when someone votes for an option that's not their first choice?
Exit shell with shortcut (not typing exit) that closes session properly
What are the consequences of changing the number of hours in a day?
Error in master's thesis, I do not know what to do
The number of Hamiltonian cycles in the complete bipartite graph
Counting Hamiltonian cycles in a grapheulerian bipartite complete graphWhat are the number of 4 cycles in the Complete Bipartite graph?Proof of Hamilton Cycle in a Complete Bipartite GraphFind and prove some needed conditions on $m,n$ for the complete bipartite graph $K_{m,n}$ to have…Hamilton cycles for bipartite graphsHamiltonian cycle that contains a specified edge in a 3-connected cubic bipartite planar Hamiltonian graphGraph theory - How many Hamiltonian Cycle in a non-complete graphWhen does a complete bipartite graph contains a Hamiltonian cicle?Counting Hamiltonian cycles in a graphNumber of Hamiltonian cycles in complete graph Kn with constraints
$begingroup$
I know that in the complete bipartite graph $K_{n,n}$ , there is $frac{n!(n-1)!}{2}$ or $n!(n-1)!$ Hamilton cycles. wiki says first, wolfram says the second one. I know that there is $2n$ ways to specify the "start", but why it goes like $n!(n-1)!$ ?
graph-theory hamiltonian-path
asked Nov 28 '15 at 10:51
BrianRBrianR
134
$endgroup$
add a comment |
$begingroup$
I know that in the complete bipartite graph $K_{n,n}$ , there is $frac{n!(n-1)!}{2}$ or $n!(n-1)!$ Hamilton cycles. wiki says first, wolfram says the second one. I know that there is $2n$ ways to specify the "start", but why it goes like $n!(n-1)!$ ?
graph-theory hamiltonian-path
asked Nov 28 '15 at 10:51
BrianRBrianR
134
$endgroup$
1
$begingroup$
Consider small examples like $K_{3,3}$ and count for yourself.
$endgroup$
– Moritz
Nov 28 '15 at 10:53
3
$begingroup$
Whether you divide by $2$ or not depends on whether you consider a cycle to be the same if you reverse its direction.
$endgroup$
– Henning Makholm
Nov 28 '15 at 11:01
add a comment |
$begingroup$
I know that in the complete bipartite graph $K_{n,n}$ , there is $frac{n!(n-1)!}{2}$ or $n!(n-1)!$ Hamilton cycles. wiki says first, wolfram says the second one. I know that there is $2n$ ways to specify the "start", but why it goes like $n!(n-1)!$ ?
graph-theory hamiltonian-path
asked Nov 28 '15 at 10:51
BrianRBrianR
134
$endgroup$
I know that in the complete bipartite graph $K_{n,n}$ , there is $frac{n!(n-1)!}{2}$ or $n!(n-1)!$ Hamilton cycles. wiki says first, wolfram says the second one. I know that there is $2n$ ways to specify the "start", but why it goes like $n!(n-1)!$ ?
graph-theory hamiltonian-path
graph-theory hamiltonian-path
asked Nov 28 '15 at 10:51
BrianRBrianR
134
asked Nov 28 '15 at 10:51
BrianRBrianR
134
edited Nov 28 '15 at 11:46
BrianR
asked Nov 28 '15 at 10:51
BrianRBrianR
134
asked Nov 28 '15 at 10:51
BrianRBrianR
134
asked Nov 28 '15 at 10:51
BrianRBrianR
134
134
1
$begingroup$
Consider small examples like $K_{3,3}$ and count for yourself.
$endgroup$
– Moritz
Nov 28 '15 at 10:53
3
$begingroup$
Whether you divide by $2$ or not depends on whether you consider a cycle to be the same if you reverse its direction.
$endgroup$
– Henning Makholm
Nov 28 '15 at 11:01
add a comment |
1
$begingroup$
Consider small examples like $K_{3,3}$ and count for yourself.
$endgroup$
– Moritz
Nov 28 '15 at 10:53
3
$begingroup$
Whether you divide by $2$ or not depends on whether you consider a cycle to be the same if you reverse its direction.
$endgroup$
– Henning Makholm
Nov 28 '15 at 11:01
1
1
$begingroup$
Consider small examples like $K_{3,3}$ and count for yourself.
$endgroup$
– Moritz
Nov 28 '15 at 10:53
$begingroup$
Consider small examples like $K_{3,3}$ and count for yourself.
$endgroup$
– Moritz
Nov 28 '15 at 10:53
3
3
$begingroup$
Whether you divide by $2$ or not depends on whether you consider a cycle to be the same if you reverse its direction.
$endgroup$
– Henning Makholm
Nov 28 '15 at 11:01
$begingroup$
Whether you divide by $2$ or not depends on whether you consider a cycle to be the same if you reverse its direction.
$endgroup$
– Henning Makholm
Nov 28 '15 at 11:01
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
As the graph is the complete bipartite graph, we can count the number of cycle as :
- Choose an initial set
- On the first set, you have $n$ choices for the first vertex
- On the second again $n$ choices
- Then $n-1$ choices
- and so on $ldots$
Therefore we count H=2(n!)(n!) Hamiltonian cycles. However, we count each cycles $2n$ times because for any cycle there are $2n$ possibles vertices acting as "start". therefore we have $$H = frac{2(n!)^2}{2n}=n!(n-1)!$$
Now, if you consider a cycle and its reverse as the same cycle, we you should divide this result by 2.
answered Feb 6 at 12:58
Thomas LesgourguesThomas Lesgourgues
1,143119
$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%2f1549694%2fthe-number-of-hamiltonian-cycles-in-the-complete-bipartite-graph%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$
As the graph is the complete bipartite graph, we can count the number of cycle as :
- Choose an initial set
- On the first set, you have $n$ choices for the first vertex
- On the second again $n$ choices
- Then $n-1$ choices
- and so on $ldots$
Therefore we count H=2(n!)(n!) Hamiltonian cycles. However, we count each cycles $2n$ times because for any cycle there are $2n$ possibles vertices acting as "start". therefore we have $$H = frac{2(n!)^2}{2n}=n!(n-1)!$$
Now, if you consider a cycle and its reverse as the same cycle, we you should divide this result by 2.
answered Feb 6 at 12:58
Thomas LesgourguesThomas Lesgourgues
1,143119
$endgroup$
add a comment |
$begingroup$
As the graph is the complete bipartite graph, we can count the number of cycle as :
- Choose an initial set
- On the first set, you have $n$ choices for the first vertex
- On the second again $n$ choices
- Then $n-1$ choices
- and so on $ldots$
Therefore we count H=2(n!)(n!) Hamiltonian cycles. However, we count each cycles $2n$ times because for any cycle there are $2n$ possibles vertices acting as "start". therefore we have $$H = frac{2(n!)^2}{2n}=n!(n-1)!$$
Now, if you consider a cycle and its reverse as the same cycle, we you should divide this result by 2.
answered Feb 6 at 12:58
Thomas LesgourguesThomas Lesgourgues
1,143119
$endgroup$
add a comment |
$begingroup$
As the graph is the complete bipartite graph, we can count the number of cycle as :
- Choose an initial set
- On the first set, you have $n$ choices for the first vertex
- On the second again $n$ choices
- Then $n-1$ choices
- and so on $ldots$
Therefore we count H=2(n!)(n!) Hamiltonian cycles. However, we count each cycles $2n$ times because for any cycle there are $2n$ possibles vertices acting as "start". therefore we have $$H = frac{2(n!)^2}{2n}=n!(n-1)!$$
Now, if you consider a cycle and its reverse as the same cycle, we you should divide this result by 2.
answered Feb 6 at 12:58
Thomas LesgourguesThomas Lesgourgues
1,143119
$endgroup$
As the graph is the complete bipartite graph, we can count the number of cycle as :
- Choose an initial set
- On the first set, you have $n$ choices for the first vertex
- On the second again $n$ choices
- Then $n-1$ choices
- and so on $ldots$
Therefore we count H=2(n!)(n!) Hamiltonian cycles. However, we count each cycles $2n$ times because for any cycle there are $2n$ possibles vertices acting as "start". therefore we have $$H = frac{2(n!)^2}{2n}=n!(n-1)!$$
Now, if you consider a cycle and its reverse as the same cycle, we you should divide this result by 2.
answered Feb 6 at 12:58
Thomas LesgourguesThomas Lesgourgues
1,143119
answered Feb 6 at 12:58
Thomas LesgourguesThomas Lesgourgues
1,143119
answered Feb 6 at 12:58
Thomas LesgourguesThomas Lesgourgues
1,143119
answered Feb 6 at 12:58
Thomas LesgourguesThomas Lesgourgues
1,143119
1,143119
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%2f1549694%2fthe-number-of-hamiltonian-cycles-in-the-complete-bipartite-graph%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
1
$begingroup$
Consider small examples like $K_{3,3}$ and count for yourself.
$endgroup$
– Moritz
Nov 28 '15 at 10:53
3
$begingroup$
Whether you divide by $2$ or not depends on whether you consider a cycle to be the same if you reverse its direction.
$endgroup$
– Henning Makholm
Nov 28 '15 at 11:01