Dtjytyk

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

1

$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

share|cite|improve this question

edited Nov 28 '15 at 11:46

BrianR

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 | 

1

$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

share|cite|improve this question

edited Nov 28 '15 at 11:46

BrianR

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

share|cite|improve this question

edited Nov 28 '15 at 11:46

BrianR

asked Nov 28 '15 at 10:51

BrianRBrianR

134

$endgroup$

share|cite|improve this question

edited Nov 28 '15 at 11:46

BrianR

asked Nov 28 '15 at 10:51

BrianRBrianR

134

share|cite|improve this question

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

1 Answer
1

active

oldest

votes

0

$begingroup$

As the graph is the complete bipartite graph, we can count the number of cycle as :

1. Choose an initial set


2. On the first set, you have $n$ choices for the first vertex


3. On the second again $n$ choices


4. Then $n-1$ choices


5. 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.

share|cite|improve this answer

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
});


}
});

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

0

$begingroup$

As the graph is the complete bipartite graph, we can count the number of cycle as :

1. Choose an initial set


2. On the first set, you have $n$ choices for the first vertex


3. On the second again $n$ choices


4. Then $n-1$ choices


5. 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.

share|cite|improve this answer

answered Feb 6 at 12:58

Thomas LesgourguesThomas Lesgourgues

1,143119

$endgroup$

add a comment | 

0

$begingroup$

As the graph is the complete bipartite graph, we can count the number of cycle as :

1. Choose an initial set


2. On the first set, you have $n$ choices for the first vertex


3. On the second again $n$ choices


4. Then $n-1$ choices


5. 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.

share|cite|improve this answer

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 :

1. Choose an initial set


2. On the first set, you have $n$ choices for the first vertex


3. On the second again $n$ choices


4. Then $n-1$ choices


5. 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.

share|cite|improve this answer

answered Feb 6 at 12:58

Thomas LesgourguesThomas Lesgourgues

1,143119

$endgroup$

share|cite|improve this answer

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