Prove Petersen graph is not Hamiltonian using deduction and no fancy theorems
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Prove Petersen graph is not Hamiltonian using basic terminology and deductions. I'm looking for an explanation without k-colouring or anything fancy like that since I haven't covered that in class. Thanks!
graph-theory
asked Feb 3 '13 at 5:13
DJ_
69711032
add a comment |Â
up vote
4
down vote
favorite
Prove Petersen graph is not Hamiltonian using basic terminology and deductions. I'm looking for an explanation without k-colouring or anything fancy like that since I haven't covered that in class. Thanks!
graph-theory
asked Feb 3 '13 at 5:13
DJ_
69711032
2
Just try "all" possibilities systematically. Take some advantage of symmetry to cut down on the work.
– André Nicolas
Feb 3 '13 at 5:16
See also math.stackexchange.com/questions/221742/…
– Gerry Myerson
Feb 3 '13 at 11:24
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Prove Petersen graph is not Hamiltonian using basic terminology and deductions. I'm looking for an explanation without k-colouring or anything fancy like that since I haven't covered that in class. Thanks!
graph-theory
asked Feb 3 '13 at 5:13
DJ_
69711032
Prove Petersen graph is not Hamiltonian using basic terminology and deductions. I'm looking for an explanation without k-colouring or anything fancy like that since I haven't covered that in class. Thanks!
graph-theory
asked Feb 3 '13 at 5:13
DJ_
69711032
asked Feb 3 '13 at 5:13
DJ_
69711032
asked Feb 3 '13 at 5:13
DJ_
69711032
asked Feb 3 '13 at 5:13
DJ_
69711032
69711032
2
Just try "all" possibilities systematically. Take some advantage of symmetry to cut down on the work.
– André Nicolas
Feb 3 '13 at 5:16
See also math.stackexchange.com/questions/221742/…
– Gerry Myerson
Feb 3 '13 at 11:24
add a comment |Â
2
Just try "all" possibilities systematically. Take some advantage of symmetry to cut down on the work.
– André Nicolas
Feb 3 '13 at 5:16
See also math.stackexchange.com/questions/221742/…
– Gerry Myerson
Feb 3 '13 at 11:24
2
2
Just try "all" possibilities systematically. Take some advantage of symmetry to cut down on the work.
– André Nicolas
Feb 3 '13 at 5:16
Just try "all" possibilities systematically. Take some advantage of symmetry to cut down on the work.
– André Nicolas
Feb 3 '13 at 5:16
See also math.stackexchange.com/questions/221742/…
– Gerry Myerson
Feb 3 '13 at 11:24
See also math.stackexchange.com/questions/221742/…
– Gerry Myerson
Feb 3 '13 at 11:24
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
8
down vote
accepted
Found at Wolfram:
The following elegant proof due to D. West demonstrates that the Petersen graph is non-Hamiltonian. If there is a $10-$cycle $C$, then the graph consists of $C$ plus five chords. If each chord joins vertices opposite on $C$, then there is a $4-$cycle. Hence some chord $e$ joins vertices at distance $4$ along $C$. Now no chord incident to a vertex opposite an endpoint of $e$ on $C$ can be added without creating a cycle with at most four vertices. Therefore, the Petersen graph is non-Hamiltonian.
There is a different simple proof here.
edited Aug 28 at 14:04
Leila
3,39742756
answered Feb 3 '13 at 11:20
Gerry Myerson
144k8145295
I never covered chords in class.
– DJ_
Feb 3 '13 at 19:12
In this context, a "chord" is just an edge joining two (non-adjacent) points on the cycle $C$. Think what a chord looks like in a circle in ordinary plane geometry, you'll get the picture.
– Gerry Myerson
Feb 3 '13 at 23:16
add a comment |Â
up vote
6
down vote
Here is a proof I like. The Petersen graph has $10$ vertices. If you have a Hamilton Cycle, it must go through each vertex. So then you draw this Hamilton cycle (just your basic cycle with $10$ vertices and $10$ edges). Now, Petersen graph has $15$ edges, so you have to add $5$ more edges to your cycle. However, any way you do this must create a $3$ or $4$ cycle, of which the graph has none. You can verify this last part for yourself and it is a simple combinatorial argument.
This type of proof is often quite effective for showing the lack of a Hamilton cycle.
edited Aug 28 at 14:03
Leila
3,39742756
answered Feb 15 '14 at 19:44
ricardio
29926
3
Not to be rude, but unless I'm missing a point, I'm wondering - how does this have more upvotes than Gerry Myerson's answer which is another wording of the exact same argument and was posted a year prior to this answer?
– Sora.
Dec 23 '17 at 23:47
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
accepted
Found at Wolfram:
The following elegant proof due to D. West demonstrates that the Petersen graph is non-Hamiltonian. If there is a $10-$cycle $C$, then the graph consists of $C$ plus five chords. If each chord joins vertices opposite on $C$, then there is a $4-$cycle. Hence some chord $e$ joins vertices at distance $4$ along $C$. Now no chord incident to a vertex opposite an endpoint of $e$ on $C$ can be added without creating a cycle with at most four vertices. Therefore, the Petersen graph is non-Hamiltonian.
There is a different simple proof here.
edited Aug 28 at 14:04
Leila
3,39742756
answered Feb 3 '13 at 11:20
Gerry Myerson
144k8145295
I never covered chords in class.
– DJ_
Feb 3 '13 at 19:12
In this context, a "chord" is just an edge joining two (non-adjacent) points on the cycle $C$. Think what a chord looks like in a circle in ordinary plane geometry, you'll get the picture.
– Gerry Myerson
Feb 3 '13 at 23:16
add a comment |Â
up vote
8
down vote
accepted
Found at Wolfram:
The following elegant proof due to D. West demonstrates that the Petersen graph is non-Hamiltonian. If there is a $10-$cycle $C$, then the graph consists of $C$ plus five chords. If each chord joins vertices opposite on $C$, then there is a $4-$cycle. Hence some chord $e$ joins vertices at distance $4$ along $C$. Now no chord incident to a vertex opposite an endpoint of $e$ on $C$ can be added without creating a cycle with at most four vertices. Therefore, the Petersen graph is non-Hamiltonian.
There is a different simple proof here.
edited Aug 28 at 14:04
Leila
3,39742756
answered Feb 3 '13 at 11:20
Gerry Myerson
144k8145295
I never covered chords in class.
– DJ_
Feb 3 '13 at 19:12
In this context, a "chord" is just an edge joining two (non-adjacent) points on the cycle $C$. Think what a chord looks like in a circle in ordinary plane geometry, you'll get the picture.
– Gerry Myerson
Feb 3 '13 at 23:16
add a comment |Â
up vote
8
down vote
accepted
up vote
8
down vote
accepted
Found at Wolfram:
The following elegant proof due to D. West demonstrates that the Petersen graph is non-Hamiltonian. If there is a $10-$cycle $C$, then the graph consists of $C$ plus five chords. If each chord joins vertices opposite on $C$, then there is a $4-$cycle. Hence some chord $e$ joins vertices at distance $4$ along $C$. Now no chord incident to a vertex opposite an endpoint of $e$ on $C$ can be added without creating a cycle with at most four vertices. Therefore, the Petersen graph is non-Hamiltonian.
There is a different simple proof here.
edited Aug 28 at 14:04
Leila
3,39742756
answered Feb 3 '13 at 11:20
Gerry Myerson
144k8145295
Found at Wolfram:
The following elegant proof due to D. West demonstrates that the Petersen graph is non-Hamiltonian. If there is a $10-$cycle $C$, then the graph consists of $C$ plus five chords. If each chord joins vertices opposite on $C$, then there is a $4-$cycle. Hence some chord $e$ joins vertices at distance $4$ along $C$. Now no chord incident to a vertex opposite an endpoint of $e$ on $C$ can be added without creating a cycle with at most four vertices. Therefore, the Petersen graph is non-Hamiltonian.
There is a different simple proof here.
edited Aug 28 at 14:04
Leila
3,39742756
answered Feb 3 '13 at 11:20
Gerry Myerson
144k8145295
edited Aug 28 at 14:04
Leila
3,39742756
edited Aug 28 at 14:04
Leila
3,39742756
edited Aug 28 at 14:04
Leila
3,39742756
3,39742756
answered Feb 3 '13 at 11:20
Gerry Myerson
144k8145295
answered Feb 3 '13 at 11:20
Gerry Myerson
144k8145295
answered Feb 3 '13 at 11:20
Gerry Myerson
144k8145295
144k8145295
I never covered chords in class.
– DJ_
Feb 3 '13 at 19:12
In this context, a "chord" is just an edge joining two (non-adjacent) points on the cycle $C$. Think what a chord looks like in a circle in ordinary plane geometry, you'll get the picture.
– Gerry Myerson
Feb 3 '13 at 23:16
add a comment |Â
I never covered chords in class.
– DJ_
Feb 3 '13 at 19:12
In this context, a "chord" is just an edge joining two (non-adjacent) points on the cycle $C$. Think what a chord looks like in a circle in ordinary plane geometry, you'll get the picture.
– Gerry Myerson
Feb 3 '13 at 23:16
I never covered chords in class.
– DJ_
Feb 3 '13 at 19:12
I never covered chords in class.
– DJ_
Feb 3 '13 at 19:12
In this context, a "chord" is just an edge joining two (non-adjacent) points on the cycle $C$. Think what a chord looks like in a circle in ordinary plane geometry, you'll get the picture.
– Gerry Myerson
Feb 3 '13 at 23:16
In this context, a "chord" is just an edge joining two (non-adjacent) points on the cycle $C$. Think what a chord looks like in a circle in ordinary plane geometry, you'll get the picture.
– Gerry Myerson
Feb 3 '13 at 23:16
add a comment |Â
up vote
6
down vote
Here is a proof I like. The Petersen graph has $10$ vertices. If you have a Hamilton Cycle, it must go through each vertex. So then you draw this Hamilton cycle (just your basic cycle with $10$ vertices and $10$ edges). Now, Petersen graph has $15$ edges, so you have to add $5$ more edges to your cycle. However, any way you do this must create a $3$ or $4$ cycle, of which the graph has none. You can verify this last part for yourself and it is a simple combinatorial argument.
This type of proof is often quite effective for showing the lack of a Hamilton cycle.
edited Aug 28 at 14:03
Leila
3,39742756
answered Feb 15 '14 at 19:44
ricardio
29926
3
Not to be rude, but unless I'm missing a point, I'm wondering - how does this have more upvotes than Gerry Myerson's answer which is another wording of the exact same argument and was posted a year prior to this answer?
– Sora.
Dec 23 '17 at 23:47
add a comment |Â
up vote
6
down vote
Here is a proof I like. The Petersen graph has $10$ vertices. If you have a Hamilton Cycle, it must go through each vertex. So then you draw this Hamilton cycle (just your basic cycle with $10$ vertices and $10$ edges). Now, Petersen graph has $15$ edges, so you have to add $5$ more edges to your cycle. However, any way you do this must create a $3$ or $4$ cycle, of which the graph has none. You can verify this last part for yourself and it is a simple combinatorial argument.
This type of proof is often quite effective for showing the lack of a Hamilton cycle.
edited Aug 28 at 14:03
Leila
3,39742756
answered Feb 15 '14 at 19:44
ricardio
29926
3
Not to be rude, but unless I'm missing a point, I'm wondering - how does this have more upvotes than Gerry Myerson's answer which is another wording of the exact same argument and was posted a year prior to this answer?
– Sora.
Dec 23 '17 at 23:47
add a comment |Â
up vote
6
down vote
up vote
6
down vote
Here is a proof I like. The Petersen graph has $10$ vertices. If you have a Hamilton Cycle, it must go through each vertex. So then you draw this Hamilton cycle (just your basic cycle with $10$ vertices and $10$ edges). Now, Petersen graph has $15$ edges, so you have to add $5$ more edges to your cycle. However, any way you do this must create a $3$ or $4$ cycle, of which the graph has none. You can verify this last part for yourself and it is a simple combinatorial argument.
This type of proof is often quite effective for showing the lack of a Hamilton cycle.
edited Aug 28 at 14:03
Leila
3,39742756
answered Feb 15 '14 at 19:44
ricardio
29926
Here is a proof I like. The Petersen graph has $10$ vertices. If you have a Hamilton Cycle, it must go through each vertex. So then you draw this Hamilton cycle (just your basic cycle with $10$ vertices and $10$ edges). Now, Petersen graph has $15$ edges, so you have to add $5$ more edges to your cycle. However, any way you do this must create a $3$ or $4$ cycle, of which the graph has none. You can verify this last part for yourself and it is a simple combinatorial argument.
This type of proof is often quite effective for showing the lack of a Hamilton cycle.
edited Aug 28 at 14:03
Leila
3,39742756
answered Feb 15 '14 at 19:44
ricardio
29926
edited Aug 28 at 14:03
Leila
3,39742756
edited Aug 28 at 14:03
Leila
3,39742756
edited Aug 28 at 14:03
Leila
3,39742756
3,39742756
answered Feb 15 '14 at 19:44
ricardio
29926
answered Feb 15 '14 at 19:44
ricardio
29926
answered Feb 15 '14 at 19:44
ricardio
29926
29926
3
Not to be rude, but unless I'm missing a point, I'm wondering - how does this have more upvotes than Gerry Myerson's answer which is another wording of the exact same argument and was posted a year prior to this answer?
– Sora.
Dec 23 '17 at 23:47
add a comment |Â
3
Not to be rude, but unless I'm missing a point, I'm wondering - how does this have more upvotes than Gerry Myerson's answer which is another wording of the exact same argument and was posted a year prior to this answer?
– Sora.
Dec 23 '17 at 23:47
3
3
Not to be rude, but unless I'm missing a point, I'm wondering - how does this have more upvotes than Gerry Myerson's answer which is another wording of the exact same argument and was posted a year prior to this answer?
– Sora.
Dec 23 '17 at 23:47
Not to be rude, but unless I'm missing a point, I'm wondering - how does this have more upvotes than Gerry Myerson's answer which is another wording of the exact same argument and was posted a year prior to this answer?
– Sora.
Dec 23 '17 at 23:47
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f293364%2fprove-petersen-graph-is-not-hamiltonian-using-deduction-and-no-fancy-theorems%23new-answer', 'question_page');
);
Post as a guest
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
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
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
2
Just try "all" possibilities systematically. Take some advantage of symmetry to cut down on the work.
– André Nicolas
Feb 3 '13 at 5:16
See also math.stackexchange.com/questions/221742/…
– Gerry Myerson
Feb 3 '13 at 11:24