Mixing
Hamiltonian paths in graph
$begingroup$
I have a theorem about Hamiltonian paths in graph, but I doubt it's possible.
Theorem If vertex $v$ of graph $G$ is not isolated, and degree of every other vertex is $geq k$ for $k geq 2$, and $|V| leq 2k-1$, then $v$ is connected by hamiltonian paths with every vertex in $G$.
Proof: Let $G'=G-v$. $|G'| leq 2k-2$, and for every two vertices of $G': deg(x)+deg(y) geq 2k-2$. It can be shown from one of the theorems, that $G'$ is hamiltonian. Now, if we join vertex $v$ to the $G'$, it'll be connected with vertices on the hamiltonian cycle, and degree of every its vertex is $geq k$. How can I, in this point, prove that $v$ is connected with every vertex of cycle by hamiltonian path?
Do you know any theorems that state about existance of various hamiltonian paths in graph, between one vertex and another set of vertices?
And do I clearly understand, that above theorem doesn't work for let's say cycle, connected with $v$ by only one edge? You cannot construct hamiltonian path between $v$ and the first vertex, to what it's connected. (In the picture: A is not connected to B by a hamiltonian path)
So, is it possible to fix the statement of this theorem, so it is true?
Thank you for any help. I'd appreciate all ideas.
proof-explanation hamiltonian-path
asked Feb 1 at 6:29
OlgaOlga
176
$endgroup$
add a comment |
$begingroup$
I have a theorem about Hamiltonian paths in graph, but I doubt it's possible.
Theorem If vertex $v$ of graph $G$ is not isolated, and degree of every other vertex is $geq k$ for $k geq 2$, and $|V| leq 2k-1$, then $v$ is connected by hamiltonian paths with every vertex in $G$.
Proof: Let $G'=G-v$. $|G'| leq 2k-2$, and for every two vertices of $G': deg(x)+deg(y) geq 2k-2$. It can be shown from one of the theorems, that $G'$ is hamiltonian. Now, if we join vertex $v$ to the $G'$, it'll be connected with vertices on the hamiltonian cycle, and degree of every its vertex is $geq k$. How can I, in this point, prove that $v$ is connected with every vertex of cycle by hamiltonian path?
Do you know any theorems that state about existance of various hamiltonian paths in graph, between one vertex and another set of vertices?
And do I clearly understand, that above theorem doesn't work for let's say cycle, connected with $v$ by only one edge? You cannot construct hamiltonian path between $v$ and the first vertex, to what it's connected. (In the picture: A is not connected to B by a hamiltonian path)
So, is it possible to fix the statement of this theorem, so it is true?
Thank you for any help. I'd appreciate all ideas.
proof-explanation hamiltonian-path
asked Feb 1 at 6:29
OlgaOlga
176
$endgroup$
$begingroup$
This theorem is from article: "On maximal paths and circuits of graphs" - Erdos, Gallai
$endgroup$
– Olga
Feb 1 at 6:32
add a comment |
$begingroup$
I have a theorem about Hamiltonian paths in graph, but I doubt it's possible.
Theorem If vertex $v$ of graph $G$ is not isolated, and degree of every other vertex is $geq k$ for $k geq 2$, and $|V| leq 2k-1$, then $v$ is connected by hamiltonian paths with every vertex in $G$.
Proof: Let $G'=G-v$. $|G'| leq 2k-2$, and for every two vertices of $G': deg(x)+deg(y) geq 2k-2$. It can be shown from one of the theorems, that $G'$ is hamiltonian. Now, if we join vertex $v$ to the $G'$, it'll be connected with vertices on the hamiltonian cycle, and degree of every its vertex is $geq k$. How can I, in this point, prove that $v$ is connected with every vertex of cycle by hamiltonian path?
Do you know any theorems that state about existance of various hamiltonian paths in graph, between one vertex and another set of vertices?
And do I clearly understand, that above theorem doesn't work for let's say cycle, connected with $v$ by only one edge? You cannot construct hamiltonian path between $v$ and the first vertex, to what it's connected. (In the picture: A is not connected to B by a hamiltonian path)
So, is it possible to fix the statement of this theorem, so it is true?
Thank you for any help. I'd appreciate all ideas.
proof-explanation hamiltonian-path
asked Feb 1 at 6:29
OlgaOlga
176
$endgroup$
I have a theorem about Hamiltonian paths in graph, but I doubt it's possible.
Theorem If vertex $v$ of graph $G$ is not isolated, and degree of every other vertex is $geq k$ for $k geq 2$, and $|V| leq 2k-1$, then $v$ is connected by hamiltonian paths with every vertex in $G$.
Proof: Let $G'=G-v$. $|G'| leq 2k-2$, and for every two vertices of $G': deg(x)+deg(y) geq 2k-2$. It can be shown from one of the theorems, that $G'$ is hamiltonian. Now, if we join vertex $v$ to the $G'$, it'll be connected with vertices on the hamiltonian cycle, and degree of every its vertex is $geq k$. How can I, in this point, prove that $v$ is connected with every vertex of cycle by hamiltonian path?
Do you know any theorems that state about existance of various hamiltonian paths in graph, between one vertex and another set of vertices?
And do I clearly understand, that above theorem doesn't work for let's say cycle, connected with $v$ by only one edge? You cannot construct hamiltonian path between $v$ and the first vertex, to what it's connected. (In the picture: A is not connected to B by a hamiltonian path)
So, is it possible to fix the statement of this theorem, so it is true?
Thank you for any help. I'd appreciate all ideas.
proof-explanation hamiltonian-path
proof-explanation hamiltonian-path
asked Feb 1 at 6:29
OlgaOlga
176
asked Feb 1 at 6:29
OlgaOlga
176
edited Feb 1 at 7:42
Olga
asked Feb 1 at 6:29
OlgaOlga
176
asked Feb 1 at 6:29
OlgaOlga
176
asked Feb 1 at 6:29
OlgaOlga
176
176
$begingroup$
This theorem is from article: "On maximal paths and circuits of graphs" - Erdos, Gallai
$endgroup$
– Olga
Feb 1 at 6:32
add a comment |
$begingroup$
This theorem is from article: "On maximal paths and circuits of graphs" - Erdos, Gallai
$endgroup$
– Olga
Feb 1 at 6:32
$begingroup$
This theorem is from article: "On maximal paths and circuits of graphs" - Erdos, Gallai
$endgroup$
– Olga
Feb 1 at 6:32
$begingroup$
This theorem is from article: "On maximal paths and circuits of graphs" - Erdos, Gallai
$endgroup$
– Olga
Feb 1 at 6:32
add a comment |
0
active
oldest
votes
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%2f3095891%2fhamiltonian-paths-in-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3095891%2fhamiltonian-paths-in-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
$begingroup$
This theorem is from article: "On maximal paths and circuits of graphs" - Erdos, Gallai
$endgroup$
– Olga
Feb 1 at 6:32