hamilton-connected graph characteristics
$begingroup$
I'm trying to understand the answer to the following question:
Prove a lower limit of $|E(G)|$ where for any $u,vin G$, there exists a Hamilton path
Define a "Hamilton-connected graph G" as
For any vertices u,v∈G, a Hamilton path exists, where the two ends of the path are vertices u and v. Try to prove that if G is a Hamilton-connected graph and |V(G)|⩾4, the following inequation holds:
|E(G)|⩾[(3|V(G)|+1)/2]
I don't the get the part he says "Since v has only two neighbors, then the first vertex in this Hamiltonian path must be v, or else v will be unreachable before reaching y. However, if the vertex v is second on the Hamiltonian path, then the only possible vertex to be third is y. But there must be at least 4 vertices so this is not a Hamiltonian path"
Why is not a Hamilton- connected?
P.D. I don't know if he means Hamiltonian or Hamilton as the definition of the problem (both are different).
graph-theory
asked Jan 17 at 18:00
John HernandezJohn Hernandez
205
$endgroup$
add a comment |
$begingroup$
I'm trying to understand the answer to the following question:
Prove a lower limit of $|E(G)|$ where for any $u,vin G$, there exists a Hamilton path
Define a "Hamilton-connected graph G" as
For any vertices u,v∈G, a Hamilton path exists, where the two ends of the path are vertices u and v. Try to prove that if G is a Hamilton-connected graph and |V(G)|⩾4, the following inequation holds:
|E(G)|⩾[(3|V(G)|+1)/2]
I don't the get the part he says "Since v has only two neighbors, then the first vertex in this Hamiltonian path must be v, or else v will be unreachable before reaching y. However, if the vertex v is second on the Hamiltonian path, then the only possible vertex to be third is y. But there must be at least 4 vertices so this is not a Hamiltonian path"
Why is not a Hamilton- connected?
P.D. I don't know if he means Hamiltonian or Hamilton as the definition of the problem (both are different).
graph-theory
asked Jan 17 at 18:00
John HernandezJohn Hernandez
205
$endgroup$
add a comment |
$begingroup$
I'm trying to understand the answer to the following question:
Prove a lower limit of $|E(G)|$ where for any $u,vin G$, there exists a Hamilton path
Define a "Hamilton-connected graph G" as
For any vertices u,v∈G, a Hamilton path exists, where the two ends of the path are vertices u and v. Try to prove that if G is a Hamilton-connected graph and |V(G)|⩾4, the following inequation holds:
|E(G)|⩾[(3|V(G)|+1)/2]
I don't the get the part he says "Since v has only two neighbors, then the first vertex in this Hamiltonian path must be v, or else v will be unreachable before reaching y. However, if the vertex v is second on the Hamiltonian path, then the only possible vertex to be third is y. But there must be at least 4 vertices so this is not a Hamiltonian path"
Why is not a Hamilton- connected?
P.D. I don't know if he means Hamiltonian or Hamilton as the definition of the problem (both are different).
graph-theory
asked Jan 17 at 18:00
John HernandezJohn Hernandez
205
$endgroup$
I'm trying to understand the answer to the following question:
Prove a lower limit of $|E(G)|$ where for any $u,vin G$, there exists a Hamilton path
Define a "Hamilton-connected graph G" as
For any vertices u,v∈G, a Hamilton path exists, where the two ends of the path are vertices u and v. Try to prove that if G is a Hamilton-connected graph and |V(G)|⩾4, the following inequation holds:
|E(G)|⩾[(3|V(G)|+1)/2]
I don't the get the part he says "Since v has only two neighbors, then the first vertex in this Hamiltonian path must be v, or else v will be unreachable before reaching y. However, if the vertex v is second on the Hamiltonian path, then the only possible vertex to be third is y. But there must be at least 4 vertices so this is not a Hamiltonian path"
Why is not a Hamilton- connected?
P.D. I don't know if he means Hamiltonian or Hamilton as the definition of the problem (both are different).
graph-theory
graph-theory
asked Jan 17 at 18:00
John HernandezJohn Hernandez
205
asked Jan 17 at 18:00
John HernandezJohn Hernandez
205
asked Jan 17 at 18:00
John HernandezJohn Hernandez
205
asked Jan 17 at 18:00
John HernandezJohn Hernandez
205
asked Jan 17 at 18:00
John HernandezJohn Hernandez
205
205
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I tried to give as much details as possible :
Suppose that $G$ is hamilton-connected, i.e. for any pair of vertices $u$, $v$, there exists an Hamiltonian path from $u$ to $v$.
Suppose that in $G$, there exists a vertex $v$ of degree only 2, and call its neighbours $x$ and $y$.
If $G$ is hamiltonian, then it must exist an hamiltonian path from $x$ to $y$. In order to be hamiltonian, this path must include $v$ (as well as all other vertices of G, once only).
In the path $(xldots y$), suppose that $v$ is not in second position, i.e. the path is $(xldots avldots y)$. But then this means that $a$ is connected to $v$. $a$ can be only equal to $x$ or $y$ (the only neighbours of $v$). $a$ cannot by $y$ as an Hamiltonian path includes each vertex only once (and this one also ends by $y$). But $a$ cannot be $x$ too. This is a contradiction. Hence $v$ is in second position in the Hamiltonian path from $x$ to $y$. Therefore the path must be $(xvldots y)$.
But from $v$, the only vertex we can reach is $y$, therefore the path is exactly $(xvy)$
However we have $|V(G)|geq 4$, therefore this path is not hamiltonian, (it would need to go throught every vertex in order to be hamiltonian). this is a contradiction.
Therefore there exist no hamiltonian path from $x$ to $y$, and then $G$ is not Hamilton-connected
answered Jan 17 at 18:16
Thomas LesgourguesThomas Lesgourgues
725117
$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%2f3077301%2fhamilton-connected-graph-characteristics%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$
I tried to give as much details as possible :
Suppose that $G$ is hamilton-connected, i.e. for any pair of vertices $u$, $v$, there exists an Hamiltonian path from $u$ to $v$.
Suppose that in $G$, there exists a vertex $v$ of degree only 2, and call its neighbours $x$ and $y$.
If $G$ is hamiltonian, then it must exist an hamiltonian path from $x$ to $y$. In order to be hamiltonian, this path must include $v$ (as well as all other vertices of G, once only).
In the path $(xldots y$), suppose that $v$ is not in second position, i.e. the path is $(xldots avldots y)$. But then this means that $a$ is connected to $v$. $a$ can be only equal to $x$ or $y$ (the only neighbours of $v$). $a$ cannot by $y$ as an Hamiltonian path includes each vertex only once (and this one also ends by $y$). But $a$ cannot be $x$ too. This is a contradiction. Hence $v$ is in second position in the Hamiltonian path from $x$ to $y$. Therefore the path must be $(xvldots y)$.
But from $v$, the only vertex we can reach is $y$, therefore the path is exactly $(xvy)$
However we have $|V(G)|geq 4$, therefore this path is not hamiltonian, (it would need to go throught every vertex in order to be hamiltonian). this is a contradiction.
Therefore there exist no hamiltonian path from $x$ to $y$, and then $G$ is not Hamilton-connected
answered Jan 17 at 18:16
Thomas LesgourguesThomas Lesgourgues
725117
$endgroup$
add a comment |
$begingroup$
I tried to give as much details as possible :
Suppose that $G$ is hamilton-connected, i.e. for any pair of vertices $u$, $v$, there exists an Hamiltonian path from $u$ to $v$.
Suppose that in $G$, there exists a vertex $v$ of degree only 2, and call its neighbours $x$ and $y$.
If $G$ is hamiltonian, then it must exist an hamiltonian path from $x$ to $y$. In order to be hamiltonian, this path must include $v$ (as well as all other vertices of G, once only).
In the path $(xldots y$), suppose that $v$ is not in second position, i.e. the path is $(xldots avldots y)$. But then this means that $a$ is connected to $v$. $a$ can be only equal to $x$ or $y$ (the only neighbours of $v$). $a$ cannot by $y$ as an Hamiltonian path includes each vertex only once (and this one also ends by $y$). But $a$ cannot be $x$ too. This is a contradiction. Hence $v$ is in second position in the Hamiltonian path from $x$ to $y$. Therefore the path must be $(xvldots y)$.
But from $v$, the only vertex we can reach is $y$, therefore the path is exactly $(xvy)$
However we have $|V(G)|geq 4$, therefore this path is not hamiltonian, (it would need to go throught every vertex in order to be hamiltonian). this is a contradiction.
Therefore there exist no hamiltonian path from $x$ to $y$, and then $G$ is not Hamilton-connected
answered Jan 17 at 18:16
Thomas LesgourguesThomas Lesgourgues
725117
$endgroup$
add a comment |
$begingroup$
I tried to give as much details as possible :
Suppose that $G$ is hamilton-connected, i.e. for any pair of vertices $u$, $v$, there exists an Hamiltonian path from $u$ to $v$.
Suppose that in $G$, there exists a vertex $v$ of degree only 2, and call its neighbours $x$ and $y$.
If $G$ is hamiltonian, then it must exist an hamiltonian path from $x$ to $y$. In order to be hamiltonian, this path must include $v$ (as well as all other vertices of G, once only).
In the path $(xldots y$), suppose that $v$ is not in second position, i.e. the path is $(xldots avldots y)$. But then this means that $a$ is connected to $v$. $a$ can be only equal to $x$ or $y$ (the only neighbours of $v$). $a$ cannot by $y$ as an Hamiltonian path includes each vertex only once (and this one also ends by $y$). But $a$ cannot be $x$ too. This is a contradiction. Hence $v$ is in second position in the Hamiltonian path from $x$ to $y$. Therefore the path must be $(xvldots y)$.
But from $v$, the only vertex we can reach is $y$, therefore the path is exactly $(xvy)$
However we have $|V(G)|geq 4$, therefore this path is not hamiltonian, (it would need to go throught every vertex in order to be hamiltonian). this is a contradiction.
Therefore there exist no hamiltonian path from $x$ to $y$, and then $G$ is not Hamilton-connected
answered Jan 17 at 18:16
Thomas LesgourguesThomas Lesgourgues
725117
$endgroup$
I tried to give as much details as possible :
Suppose that $G$ is hamilton-connected, i.e. for any pair of vertices $u$, $v$, there exists an Hamiltonian path from $u$ to $v$.
Suppose that in $G$, there exists a vertex $v$ of degree only 2, and call its neighbours $x$ and $y$.
If $G$ is hamiltonian, then it must exist an hamiltonian path from $x$ to $y$. In order to be hamiltonian, this path must include $v$ (as well as all other vertices of G, once only).
In the path $(xldots y$), suppose that $v$ is not in second position, i.e. the path is $(xldots avldots y)$. But then this means that $a$ is connected to $v$. $a$ can be only equal to $x$ or $y$ (the only neighbours of $v$). $a$ cannot by $y$ as an Hamiltonian path includes each vertex only once (and this one also ends by $y$). But $a$ cannot be $x$ too. This is a contradiction. Hence $v$ is in second position in the Hamiltonian path from $x$ to $y$. Therefore the path must be $(xvldots y)$.
But from $v$, the only vertex we can reach is $y$, therefore the path is exactly $(xvy)$
However we have $|V(G)|geq 4$, therefore this path is not hamiltonian, (it would need to go throught every vertex in order to be hamiltonian). this is a contradiction.
Therefore there exist no hamiltonian path from $x$ to $y$, and then $G$ is not Hamilton-connected
answered Jan 17 at 18:16
Thomas LesgourguesThomas Lesgourgues
725117
edited Jan 17 at 18:23
answered Jan 17 at 18:16
Thomas LesgourguesThomas Lesgourgues
725117
answered Jan 17 at 18:16
Thomas LesgourguesThomas Lesgourgues
725117
answered Jan 17 at 18:16
Thomas LesgourguesThomas Lesgourgues
725117
725117
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%2f3077301%2fhamilton-connected-graph-characteristics%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
