How many Hamiltonian cycles are there in a complete graph if we discount the cycle's orientation or starting...
Consider a complete graph G with n vertices.
Each vertex is indexed by [n] = {1,2,3...n} where n >= 4.
In this case, a Hamiltonian cycle is determined only by the collection of edges it contains, and we do not need to consider its orientation or starting point.
Question:
- How many Hamiltonian cycles are there in G?
- How many Hamiltonian cycles in G contains the edge {1,2}?
- How many Hamiltonian cycles in G contains the edge {1,2} and {2,3}?
- How many Hamiltonian cycles in G contains the edge {1,2} and {3,4}?
- Suppose that M is a set of k <= (n/2) edges, in which no two edges in M share a vertex. How many Hamiltonian cycles contain all edges in M? Give answer in terms of k and n
- How many Hamiltonian cycles in G do not contain the edge {1,2}, {2,3} and {3,4}?
The question really clusters into two parts.
PART 1: How do I discount "orientation" and "starting point"?
This has to do with 1, 2, 3, 4, and 6.
I can calculate the combinations of edges there can be, but that's not what they're asking. They only want the combinations that form a Hamiltonian cycle.
Additionally, I don't see how you can just know whether a Hamiltonian cycle has crossed through a certain edge.
The more I think about it, the more I feel this is about combinatorial numbers as opposed to graph theory. Are they trying to trick me?
PART 2: How many cycles contain a set of edges that do not share a vertex.
This has to do with question 5, specifically.
My first response is "none..."?
If the graph is a complete graph, then all edges share a vertex at some point right? In that case, M seems to be an empty set and there are no Hamiltonian cycles that cover it. But that doesn't feel right at all...
graph-theory hamiltonian-path
asked Nov 29 '18 at 21:41
potatoguypotatoguy
525
add a comment |
Consider a complete graph G with n vertices.
Each vertex is indexed by [n] = {1,2,3...n} where n >= 4.
In this case, a Hamiltonian cycle is determined only by the collection of edges it contains, and we do not need to consider its orientation or starting point.
Question:
- How many Hamiltonian cycles are there in G?
- How many Hamiltonian cycles in G contains the edge {1,2}?
- How many Hamiltonian cycles in G contains the edge {1,2} and {2,3}?
- How many Hamiltonian cycles in G contains the edge {1,2} and {3,4}?
- Suppose that M is a set of k <= (n/2) edges, in which no two edges in M share a vertex. How many Hamiltonian cycles contain all edges in M? Give answer in terms of k and n
- How many Hamiltonian cycles in G do not contain the edge {1,2}, {2,3} and {3,4}?
The question really clusters into two parts.
PART 1: How do I discount "orientation" and "starting point"?
This has to do with 1, 2, 3, 4, and 6.
I can calculate the combinations of edges there can be, but that's not what they're asking. They only want the combinations that form a Hamiltonian cycle.
Additionally, I don't see how you can just know whether a Hamiltonian cycle has crossed through a certain edge.
The more I think about it, the more I feel this is about combinatorial numbers as opposed to graph theory. Are they trying to trick me?
PART 2: How many cycles contain a set of edges that do not share a vertex.
This has to do with question 5, specifically.
My first response is "none..."?
If the graph is a complete graph, then all edges share a vertex at some point right? In that case, M seems to be an empty set and there are no Hamiltonian cycles that cover it. But that doesn't feel right at all...
graph-theory hamiltonian-path
asked Nov 29 '18 at 21:41
potatoguypotatoguy
525
add a comment |
Consider a complete graph G with n vertices.
Each vertex is indexed by [n] = {1,2,3...n} where n >= 4.
In this case, a Hamiltonian cycle is determined only by the collection of edges it contains, and we do not need to consider its orientation or starting point.
Question:
- How many Hamiltonian cycles are there in G?
- How many Hamiltonian cycles in G contains the edge {1,2}?
- How many Hamiltonian cycles in G contains the edge {1,2} and {2,3}?
- How many Hamiltonian cycles in G contains the edge {1,2} and {3,4}?
- Suppose that M is a set of k <= (n/2) edges, in which no two edges in M share a vertex. How many Hamiltonian cycles contain all edges in M? Give answer in terms of k and n
- How many Hamiltonian cycles in G do not contain the edge {1,2}, {2,3} and {3,4}?
The question really clusters into two parts.
PART 1: How do I discount "orientation" and "starting point"?
This has to do with 1, 2, 3, 4, and 6.
I can calculate the combinations of edges there can be, but that's not what they're asking. They only want the combinations that form a Hamiltonian cycle.
Additionally, I don't see how you can just know whether a Hamiltonian cycle has crossed through a certain edge.
The more I think about it, the more I feel this is about combinatorial numbers as opposed to graph theory. Are they trying to trick me?
PART 2: How many cycles contain a set of edges that do not share a vertex.
This has to do with question 5, specifically.
My first response is "none..."?
If the graph is a complete graph, then all edges share a vertex at some point right? In that case, M seems to be an empty set and there are no Hamiltonian cycles that cover it. But that doesn't feel right at all...
graph-theory hamiltonian-path
asked Nov 29 '18 at 21:41
potatoguypotatoguy
525
Consider a complete graph G with n vertices.
Each vertex is indexed by [n] = {1,2,3...n} where n >= 4.
In this case, a Hamiltonian cycle is determined only by the collection of edges it contains, and we do not need to consider its orientation or starting point.
Question:
- How many Hamiltonian cycles are there in G?
- How many Hamiltonian cycles in G contains the edge {1,2}?
- How many Hamiltonian cycles in G contains the edge {1,2} and {2,3}?
- How many Hamiltonian cycles in G contains the edge {1,2} and {3,4}?
- Suppose that M is a set of k <= (n/2) edges, in which no two edges in M share a vertex. How many Hamiltonian cycles contain all edges in M? Give answer in terms of k and n
- How many Hamiltonian cycles in G do not contain the edge {1,2}, {2,3} and {3,4}?
The question really clusters into two parts.
PART 1: How do I discount "orientation" and "starting point"?
This has to do with 1, 2, 3, 4, and 6.
I can calculate the combinations of edges there can be, but that's not what they're asking. They only want the combinations that form a Hamiltonian cycle.
Additionally, I don't see how you can just know whether a Hamiltonian cycle has crossed through a certain edge.
The more I think about it, the more I feel this is about combinatorial numbers as opposed to graph theory. Are they trying to trick me?
PART 2: How many cycles contain a set of edges that do not share a vertex.
This has to do with question 5, specifically.
My first response is "none..."?
If the graph is a complete graph, then all edges share a vertex at some point right? In that case, M seems to be an empty set and there are no Hamiltonian cycles that cover it. But that doesn't feel right at all...
graph-theory hamiltonian-path
graph-theory hamiltonian-path
asked Nov 29 '18 at 21:41
potatoguypotatoguy
525
asked Nov 29 '18 at 21:41
potatoguypotatoguy
525
asked Nov 29 '18 at 21:41
potatoguypotatoguy
525
asked Nov 29 '18 at 21:41
potatoguypotatoguy
525
asked Nov 29 '18 at 21:41
potatoguypotatoguy
525
525
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
Hint: if we do consider starting point and orientation, then the number of Hamiltonian cycles is the number of ways that we can order $[n]$, i.e. the number of permutations. If you know the order in which to visit the vertices, this tells you exactly the cycle. Each cycle is then counted $n$ times for each possible starting point, and twice for each direction around the cycle.
Hint for part 2: A cycle can contain ${ 1,2 }$ and ${ 3,4 }$ if it (for example) also contains edge ${ 2,3 }$.
answered Nov 29 '18 at 21:49
Puck RombachPuck Rombach
1266
Thanks for the hint, here's what I wrote for questions: Q1) n! / 2n, Q2: (n-2)!, Q3: (n-3)!
– potatoguy
Nov 30 '18 at 2:58
I'm still stuck on Q4, since the graph is separated into two sections. Do you happen to have more advise on how to approach this problem? I'm testing it out on a complete graph K5 (result seems to be 4), but I'm still trying to see how I reach this solution.
– potatoguy
Nov 30 '18 at 3:05
Well, you could try treating vxs 1 and 2 as a single vx (and same for 3 and 4), then find the number of cycles. But remember both these edges can appear in two directions on a cycle.
– Puck Rombach
Nov 30 '18 at 3:12
add a comment |
Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)! (e) can brake into (12)(34)(56)789 and applying counting,answer=(n)!(n-k-1)!/(2n) (f)Obviously Answer=1/2(n-1)!-(n-3)!
answered Nov 30 '18 at 9:23
zacahryzacahry
1
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%2f3019257%2fhow-many-hamiltonian-cycles-are-there-in-a-complete-graph-if-we-discount-the-cyc%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Hint: if we do consider starting point and orientation, then the number of Hamiltonian cycles is the number of ways that we can order $[n]$, i.e. the number of permutations. If you know the order in which to visit the vertices, this tells you exactly the cycle. Each cycle is then counted $n$ times for each possible starting point, and twice for each direction around the cycle.
Hint for part 2: A cycle can contain ${ 1,2 }$ and ${ 3,4 }$ if it (for example) also contains edge ${ 2,3 }$.
answered Nov 29 '18 at 21:49
Puck RombachPuck Rombach
1266
Thanks for the hint, here's what I wrote for questions: Q1) n! / 2n, Q2: (n-2)!, Q3: (n-3)!
– potatoguy
Nov 30 '18 at 2:58
I'm still stuck on Q4, since the graph is separated into two sections. Do you happen to have more advise on how to approach this problem? I'm testing it out on a complete graph K5 (result seems to be 4), but I'm still trying to see how I reach this solution.
– potatoguy
Nov 30 '18 at 3:05
Well, you could try treating vxs 1 and 2 as a single vx (and same for 3 and 4), then find the number of cycles. But remember both these edges can appear in two directions on a cycle.
– Puck Rombach
Nov 30 '18 at 3:12
add a comment |
Hint: if we do consider starting point and orientation, then the number of Hamiltonian cycles is the number of ways that we can order $[n]$, i.e. the number of permutations. If you know the order in which to visit the vertices, this tells you exactly the cycle. Each cycle is then counted $n$ times for each possible starting point, and twice for each direction around the cycle.
Hint for part 2: A cycle can contain ${ 1,2 }$ and ${ 3,4 }$ if it (for example) also contains edge ${ 2,3 }$.
answered Nov 29 '18 at 21:49
Puck RombachPuck Rombach
1266
Thanks for the hint, here's what I wrote for questions: Q1) n! / 2n, Q2: (n-2)!, Q3: (n-3)!
– potatoguy
Nov 30 '18 at 2:58
I'm still stuck on Q4, since the graph is separated into two sections. Do you happen to have more advise on how to approach this problem? I'm testing it out on a complete graph K5 (result seems to be 4), but I'm still trying to see how I reach this solution.
– potatoguy
Nov 30 '18 at 3:05
Well, you could try treating vxs 1 and 2 as a single vx (and same for 3 and 4), then find the number of cycles. But remember both these edges can appear in two directions on a cycle.
– Puck Rombach
Nov 30 '18 at 3:12
add a comment |
Hint: if we do consider starting point and orientation, then the number of Hamiltonian cycles is the number of ways that we can order $[n]$, i.e. the number of permutations. If you know the order in which to visit the vertices, this tells you exactly the cycle. Each cycle is then counted $n$ times for each possible starting point, and twice for each direction around the cycle.
Hint for part 2: A cycle can contain ${ 1,2 }$ and ${ 3,4 }$ if it (for example) also contains edge ${ 2,3 }$.
answered Nov 29 '18 at 21:49
Puck RombachPuck Rombach
1266
Hint: if we do consider starting point and orientation, then the number of Hamiltonian cycles is the number of ways that we can order $[n]$, i.e. the number of permutations. If you know the order in which to visit the vertices, this tells you exactly the cycle. Each cycle is then counted $n$ times for each possible starting point, and twice for each direction around the cycle.
Hint for part 2: A cycle can contain ${ 1,2 }$ and ${ 3,4 }$ if it (for example) also contains edge ${ 2,3 }$.
answered Nov 29 '18 at 21:49
Puck RombachPuck Rombach
1266
answered Nov 29 '18 at 21:49
Puck RombachPuck Rombach
1266
answered Nov 29 '18 at 21:49
Puck RombachPuck Rombach
1266
answered Nov 29 '18 at 21:49
Puck RombachPuck Rombach
1266
1266
Thanks for the hint, here's what I wrote for questions: Q1) n! / 2n, Q2: (n-2)!, Q3: (n-3)!
– potatoguy
Nov 30 '18 at 2:58
I'm still stuck on Q4, since the graph is separated into two sections. Do you happen to have more advise on how to approach this problem? I'm testing it out on a complete graph K5 (result seems to be 4), but I'm still trying to see how I reach this solution.
– potatoguy
Nov 30 '18 at 3:05
Well, you could try treating vxs 1 and 2 as a single vx (and same for 3 and 4), then find the number of cycles. But remember both these edges can appear in two directions on a cycle.
– Puck Rombach
Nov 30 '18 at 3:12
add a comment |
Thanks for the hint, here's what I wrote for questions: Q1) n! / 2n, Q2: (n-2)!, Q3: (n-3)!
– potatoguy
Nov 30 '18 at 2:58
I'm still stuck on Q4, since the graph is separated into two sections. Do you happen to have more advise on how to approach this problem? I'm testing it out on a complete graph K5 (result seems to be 4), but I'm still trying to see how I reach this solution.
– potatoguy
Nov 30 '18 at 3:05
Well, you could try treating vxs 1 and 2 as a single vx (and same for 3 and 4), then find the number of cycles. But remember both these edges can appear in two directions on a cycle.
– Puck Rombach
Nov 30 '18 at 3:12
Thanks for the hint, here's what I wrote for questions: Q1) n! / 2n, Q2: (n-2)!, Q3: (n-3)!
– potatoguy
Nov 30 '18 at 2:58
Thanks for the hint, here's what I wrote for questions: Q1) n! / 2n, Q2: (n-2)!, Q3: (n-3)!
– potatoguy
Nov 30 '18 at 2:58
I'm still stuck on Q4, since the graph is separated into two sections. Do you happen to have more advise on how to approach this problem? I'm testing it out on a complete graph K5 (result seems to be 4), but I'm still trying to see how I reach this solution.
– potatoguy
Nov 30 '18 at 3:05
I'm still stuck on Q4, since the graph is separated into two sections. Do you happen to have more advise on how to approach this problem? I'm testing it out on a complete graph K5 (result seems to be 4), but I'm still trying to see how I reach this solution.
– potatoguy
Nov 30 '18 at 3:05
Well, you could try treating vxs 1 and 2 as a single vx (and same for 3 and 4), then find the number of cycles. But remember both these edges can appear in two directions on a cycle.
– Puck Rombach
Nov 30 '18 at 3:12
Well, you could try treating vxs 1 and 2 as a single vx (and same for 3 and 4), then find the number of cycles. But remember both these edges can appear in two directions on a cycle.
– Puck Rombach
Nov 30 '18 at 3:12
add a comment |
Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)! (e) can brake into (12)(34)(56)789 and applying counting,answer=(n)!(n-k-1)!/(2n) (f)Obviously Answer=1/2(n-1)!-(n-3)!
answered Nov 30 '18 at 9:23
zacahryzacahry
1
add a comment |
Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)! (e) can brake into (12)(34)(56)789 and applying counting,answer=(n)!(n-k-1)!/(2n) (f)Obviously Answer=1/2(n-1)!-(n-3)!
answered Nov 30 '18 at 9:23
zacahryzacahry
1
add a comment |
Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)! (e) can brake into (12)(34)(56)789 and applying counting,answer=(n)!(n-k-1)!/(2n) (f)Obviously Answer=1/2(n-1)!-(n-3)!
answered Nov 30 '18 at 9:23
zacahryzacahry
1
Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)! (e) can brake into (12)(34)(56)789 and applying counting,answer=(n)!(n-k-1)!/(2n) (f)Obviously Answer=1/2(n-1)!-(n-3)!
answered Nov 30 '18 at 9:23
zacahryzacahry
1
answered Nov 30 '18 at 9:23
zacahryzacahry
1
answered Nov 30 '18 at 9:23
zacahryzacahry
1
answered Nov 30 '18 at 9:23
zacahryzacahry
1
1
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%2f3019257%2fhow-many-hamiltonian-cycles-are-there-in-a-complete-graph-if-we-discount-the-cyc%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
