Mixing
Every self-complementary graph contains a Hamiltonian path.
$begingroup$
How to show that every self-complementary graph is traceable (contains a Hamiltonian path)?
Definitions:
Self-complementary graph
Hamiltonian-Path
Traceable Graph
graph-theory hamiltonian-path
edited Jan 30 at 13:57
J. W. Tanner
4,4401320
asked Jan 30 at 12:11
Ayush ChaurasiaAyush Chaurasia
12
$endgroup$
add a comment |
$begingroup$
How to show that every self-complementary graph is traceable (contains a Hamiltonian path)?
Definitions:
Self-complementary graph
Hamiltonian-Path
Traceable Graph
graph-theory hamiltonian-path
edited Jan 30 at 13:57
J. W. Tanner
4,4401320
asked Jan 30 at 12:11
Ayush ChaurasiaAyush Chaurasia
12
$endgroup$
$begingroup$
Hi, could you give us some context? What do you know in graph theory? what have you tried to solve the problem?
$endgroup$
– Thomas Lesgourgues
Jan 30 at 12:14
$begingroup$
Your source for the definition of “traceable” links to a pdf of a thesis by Ferrugia which contains a proof of the result you want. Also note that not all self-complementary graphs have Hamilton cycles - $P_4$ for example.
$endgroup$
– Chris Godsil
Jan 30 at 12:48
add a comment |
$begingroup$
How to show that every self-complementary graph is traceable (contains a Hamiltonian path)?
Definitions:
Self-complementary graph
Hamiltonian-Path
Traceable Graph
graph-theory hamiltonian-path
edited Jan 30 at 13:57
J. W. Tanner
4,4401320
asked Jan 30 at 12:11
Ayush ChaurasiaAyush Chaurasia
12
$endgroup$
How to show that every self-complementary graph is traceable (contains a Hamiltonian path)?
Definitions:
Self-complementary graph
Hamiltonian-Path
Traceable Graph
graph-theory hamiltonian-path
graph-theory hamiltonian-path
edited Jan 30 at 13:57
J. W. Tanner
4,4401320
asked Jan 30 at 12:11
Ayush ChaurasiaAyush Chaurasia
12
edited Jan 30 at 13:57
J. W. Tanner
4,4401320
asked Jan 30 at 12:11
Ayush ChaurasiaAyush Chaurasia
12
edited Jan 30 at 13:57
J. W. Tanner
4,4401320
edited Jan 30 at 13:57
J. W. Tanner
4,4401320
edited Jan 30 at 13:57
J. W. Tanner
4,4401320
4,4401320
asked Jan 30 at 12:11
Ayush ChaurasiaAyush Chaurasia
12
asked Jan 30 at 12:11
Ayush ChaurasiaAyush Chaurasia
12
asked Jan 30 at 12:11
Ayush ChaurasiaAyush Chaurasia
12
12
$begingroup$
Hi, could you give us some context? What do you know in graph theory? what have you tried to solve the problem?
$endgroup$
– Thomas Lesgourgues
Jan 30 at 12:14
$begingroup$
Your source for the definition of “traceable” links to a pdf of a thesis by Ferrugia which contains a proof of the result you want. Also note that not all self-complementary graphs have Hamilton cycles - $P_4$ for example.
$endgroup$
– Chris Godsil
Jan 30 at 12:48
add a comment |
$begingroup$
Hi, could you give us some context? What do you know in graph theory? what have you tried to solve the problem?
$endgroup$
– Thomas Lesgourgues
Jan 30 at 12:14
$begingroup$
Your source for the definition of “traceable” links to a pdf of a thesis by Ferrugia which contains a proof of the result you want. Also note that not all self-complementary graphs have Hamilton cycles - $P_4$ for example.
$endgroup$
– Chris Godsil
Jan 30 at 12:48
$begingroup$
Hi, could you give us some context? What do you know in graph theory? what have you tried to solve the problem?
$endgroup$
– Thomas Lesgourgues
Jan 30 at 12:14
$begingroup$
Hi, could you give us some context? What do you know in graph theory? what have you tried to solve the problem?
$endgroup$
– Thomas Lesgourgues
Jan 30 at 12:14
$begingroup$
Your source for the definition of “traceable” links to a pdf of a thesis by Ferrugia which contains a proof of the result you want. Also note that not all self-complementary graphs have Hamilton cycles - $P_4$ for example.
$endgroup$
– Chris Godsil
Jan 30 at 12:48
$begingroup$
Your source for the definition of “traceable” links to a pdf of a thesis by Ferrugia which contains a proof of the result you want. Also note that not all self-complementary graphs have Hamilton cycles - $P_4$ for example.
$endgroup$
– Chris Godsil
Jan 30 at 12:48
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You can order the vertices of $G$ such that
$$d_1 leq ldots leq d_n$$
Now, because $G$ is self-complementary, you can check that its vertices verify ($d_i$ correspondant to $d_{n+1-i}$ in its complementary):
$$ d_i leq i-1 < frac{n+1}{2} Rightarrow d_{n+1-i} geq n-i$$
Let $G'$ be a graph built from $G$, adding one vertex $u$, connected to all vertices of $G$. Then the vertices of $G'$ verify
$$ d_i leq i < frac{n}{2} Rightarrow d_{n-i} geq n-i$$
This is the condition for Chvatal's theorem, hence $G'$ contains a Hamiltonian circuit. Then by deleting $u$, G must contain a Hamiltonian path.
Edit
See here, p164-165 for a proof of Chvatal's theorem. This is a proof by contraposition. The key point is to take $G$ as maximal non-hamiltonian, i.e. the addition of any edge would make $G$ hamiltonian. Therefore $G$ must include an hamiltonian path (remember that hamiltonian = cyle, minus an edge = path). And then working on some maximal degree vertices, you reach the above inequalities
answered Jan 30 at 12:47
Thomas LesgourguesThomas Lesgourgues
1,285220
$endgroup$
$begingroup$
Can you explain what is the Chvatal's theorem proof? Also, is there any alternate proof for this?
$endgroup$
– Ayush Chaurasia
Jan 30 at 13:42
$begingroup$
I edited the post, with a link to the proof
$endgroup$
– Thomas Lesgourgues
Jan 30 at 15:12
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%2f3093454%2fevery-self-complementary-graph-contains-a-hamiltonian-path%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$
You can order the vertices of $G$ such that
$$d_1 leq ldots leq d_n$$
Now, because $G$ is self-complementary, you can check that its vertices verify ($d_i$ correspondant to $d_{n+1-i}$ in its complementary):
$$ d_i leq i-1 < frac{n+1}{2} Rightarrow d_{n+1-i} geq n-i$$
Let $G'$ be a graph built from $G$, adding one vertex $u$, connected to all vertices of $G$. Then the vertices of $G'$ verify
$$ d_i leq i < frac{n}{2} Rightarrow d_{n-i} geq n-i$$
This is the condition for Chvatal's theorem, hence $G'$ contains a Hamiltonian circuit. Then by deleting $u$, G must contain a Hamiltonian path.
Edit
See here, p164-165 for a proof of Chvatal's theorem. This is a proof by contraposition. The key point is to take $G$ as maximal non-hamiltonian, i.e. the addition of any edge would make $G$ hamiltonian. Therefore $G$ must include an hamiltonian path (remember that hamiltonian = cyle, minus an edge = path). And then working on some maximal degree vertices, you reach the above inequalities
answered Jan 30 at 12:47
Thomas LesgourguesThomas Lesgourgues
1,285220
$endgroup$
$begingroup$
Can you explain what is the Chvatal's theorem proof? Also, is there any alternate proof for this?
$endgroup$
– Ayush Chaurasia
Jan 30 at 13:42
$begingroup$
I edited the post, with a link to the proof
$endgroup$
– Thomas Lesgourgues
Jan 30 at 15:12
add a comment |
$begingroup$
You can order the vertices of $G$ such that
$$d_1 leq ldots leq d_n$$
Now, because $G$ is self-complementary, you can check that its vertices verify ($d_i$ correspondant to $d_{n+1-i}$ in its complementary):
$$ d_i leq i-1 < frac{n+1}{2} Rightarrow d_{n+1-i} geq n-i$$
Let $G'$ be a graph built from $G$, adding one vertex $u$, connected to all vertices of $G$. Then the vertices of $G'$ verify
$$ d_i leq i < frac{n}{2} Rightarrow d_{n-i} geq n-i$$
This is the condition for Chvatal's theorem, hence $G'$ contains a Hamiltonian circuit. Then by deleting $u$, G must contain a Hamiltonian path.
Edit
See here, p164-165 for a proof of Chvatal's theorem. This is a proof by contraposition. The key point is to take $G$ as maximal non-hamiltonian, i.e. the addition of any edge would make $G$ hamiltonian. Therefore $G$ must include an hamiltonian path (remember that hamiltonian = cyle, minus an edge = path). And then working on some maximal degree vertices, you reach the above inequalities
answered Jan 30 at 12:47
Thomas LesgourguesThomas Lesgourgues
1,285220
$endgroup$
$begingroup$
Can you explain what is the Chvatal's theorem proof? Also, is there any alternate proof for this?
$endgroup$
– Ayush Chaurasia
Jan 30 at 13:42
$begingroup$
I edited the post, with a link to the proof
$endgroup$
– Thomas Lesgourgues
Jan 30 at 15:12
add a comment |
$begingroup$
You can order the vertices of $G$ such that
$$d_1 leq ldots leq d_n$$
Now, because $G$ is self-complementary, you can check that its vertices verify ($d_i$ correspondant to $d_{n+1-i}$ in its complementary):
$$ d_i leq i-1 < frac{n+1}{2} Rightarrow d_{n+1-i} geq n-i$$
Let $G'$ be a graph built from $G$, adding one vertex $u$, connected to all vertices of $G$. Then the vertices of $G'$ verify
$$ d_i leq i < frac{n}{2} Rightarrow d_{n-i} geq n-i$$
This is the condition for Chvatal's theorem, hence $G'$ contains a Hamiltonian circuit. Then by deleting $u$, G must contain a Hamiltonian path.
Edit
See here, p164-165 for a proof of Chvatal's theorem. This is a proof by contraposition. The key point is to take $G$ as maximal non-hamiltonian, i.e. the addition of any edge would make $G$ hamiltonian. Therefore $G$ must include an hamiltonian path (remember that hamiltonian = cyle, minus an edge = path). And then working on some maximal degree vertices, you reach the above inequalities
answered Jan 30 at 12:47
Thomas LesgourguesThomas Lesgourgues
1,285220
$endgroup$
You can order the vertices of $G$ such that
$$d_1 leq ldots leq d_n$$
Now, because $G$ is self-complementary, you can check that its vertices verify ($d_i$ correspondant to $d_{n+1-i}$ in its complementary):
$$ d_i leq i-1 < frac{n+1}{2} Rightarrow d_{n+1-i} geq n-i$$
Let $G'$ be a graph built from $G$, adding one vertex $u$, connected to all vertices of $G$. Then the vertices of $G'$ verify
$$ d_i leq i < frac{n}{2} Rightarrow d_{n-i} geq n-i$$
This is the condition for Chvatal's theorem, hence $G'$ contains a Hamiltonian circuit. Then by deleting $u$, G must contain a Hamiltonian path.
Edit
See here, p164-165 for a proof of Chvatal's theorem. This is a proof by contraposition. The key point is to take $G$ as maximal non-hamiltonian, i.e. the addition of any edge would make $G$ hamiltonian. Therefore $G$ must include an hamiltonian path (remember that hamiltonian = cyle, minus an edge = path). And then working on some maximal degree vertices, you reach the above inequalities
answered Jan 30 at 12:47
Thomas LesgourguesThomas Lesgourgues
1,285220
edited Jan 30 at 15:07
answered Jan 30 at 12:47
Thomas LesgourguesThomas Lesgourgues
1,285220
answered Jan 30 at 12:47
Thomas LesgourguesThomas Lesgourgues
1,285220
answered Jan 30 at 12:47
Thomas LesgourguesThomas Lesgourgues
1,285220
1,285220
$begingroup$
Can you explain what is the Chvatal's theorem proof? Also, is there any alternate proof for this?
$endgroup$
– Ayush Chaurasia
Jan 30 at 13:42
$begingroup$
I edited the post, with a link to the proof
$endgroup$
– Thomas Lesgourgues
Jan 30 at 15:12
add a comment |
$begingroup$
Can you explain what is the Chvatal's theorem proof? Also, is there any alternate proof for this?
$endgroup$
– Ayush Chaurasia
Jan 30 at 13:42
$begingroup$
I edited the post, with a link to the proof
$endgroup$
– Thomas Lesgourgues
Jan 30 at 15:12
$begingroup$
Can you explain what is the Chvatal's theorem proof? Also, is there any alternate proof for this?
$endgroup$
– Ayush Chaurasia
Jan 30 at 13:42
$begingroup$
Can you explain what is the Chvatal's theorem proof? Also, is there any alternate proof for this?
$endgroup$
– Ayush Chaurasia
Jan 30 at 13:42
$begingroup$
I edited the post, with a link to the proof
$endgroup$
– Thomas Lesgourgues
Jan 30 at 15:12
$begingroup$
I edited the post, with a link to the proof
$endgroup$
– Thomas Lesgourgues
Jan 30 at 15:12
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%2f3093454%2fevery-self-complementary-graph-contains-a-hamiltonian-path%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
$begingroup$
Hi, could you give us some context? What do you know in graph theory? what have you tried to solve the problem?
$endgroup$
– Thomas Lesgourgues
Jan 30 at 12:14
$begingroup$
Your source for the definition of “traceable” links to a pdf of a thesis by Ferrugia which contains a proof of the result you want. Also note that not all self-complementary graphs have Hamilton cycles - $P_4$ for example.
$endgroup$
– Chris Godsil
Jan 30 at 12:48