Prove Petersen graph is not Hamiltonian using deduction and no fancy theorems

Multi tool use
Multi tool use

The name of the pictureThe name of the pictureThe name of the pictureClash 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




share|cite|improve this question
















  • 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














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




share|cite|improve this question
















  • 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












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




share|cite|improve this question












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





share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










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












  • 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










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.






share|cite|improve this answer






















  • 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

















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.






share|cite|improve this answer


















  • 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










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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













 

draft saved


draft discarded


















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

















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.






share|cite|improve this answer






















  • 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














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.






share|cite|improve this answer






















  • 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












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.






share|cite|improve this answer














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.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Aug 28 at 14:04









Leila

3,39742756




3,39742756










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
















  • 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










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.






share|cite|improve this answer


















  • 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














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.






share|cite|improve this answer


















  • 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












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.






share|cite|improve this answer














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.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Aug 28 at 14:03









Leila

3,39742756




3,39742756










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












  • 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

















 

draft saved


draft discarded















































 


draft saved


draft discarded














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
































































M0Z1eZRJi8O8wjQBE nN5
-
jUxWaS4mio4

這個網誌中的熱門文章

How to combine Bézier curves to a surface?

圖片
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite My aim is to smooth the terrain in a video game. Therefore I contrived an algorithm that makes use of Bézier curves of different orders. But this algorithm is defined in a two dimensional space for now. To shift it into the third dimension I need to somehow combine the Bézier curves. Given two curves in each two dimensions, how can I combine them to build a surface? I thought about something like a curve of a curve. Or maybe I could multiply them somehow. How can I combine them to cause the wanted behavior? Is there a common approach? In the image you can see the input, on the left, and the output, on the right, of the algorithm that works in a two dimensional space. For the real application there is a three dimensional input. The algorithm relays only on the adjacent tiles. Given these it will define the control points of the mentioned Bézier cur...
閱讀完整內容

Propositional logic and tautologies

圖片
Clash Royale CLAN TAG #URR8PPP up vote 0 down vote favorite Taken from P. Suppes "Introduction to logic" pp16 Starting from the sentence "If $P$ tautologically implies $Q$, then.." Question: Is it true that, at least within propositional logic, we are able to prove only tautologies or do I mis-understand something? If yes, is propositional logic special in some way? Is the notion of tautology meaningful only in propositional logic? logic propositional-calculus share | cite | improve this question edited Nov 29 '17 at 18:53 Mauro ALLEGRANZA 60.8k 4 46 105 asked Nov 29 '17 at 16:32 Alvin Lepik 2,448 9 20 add a comment  |  up vote 0 down vote favorite Taken from P. Suppes "Introduction to logic" pp16 Starting from the sentence "If $P$ tautologically implies $Q$, then.." Question: Is it true that, at least within propositional logic, we are able to prove only tautologi...
閱讀完整內容

Distribution of Stopped Wiener Process with Stochastic Volatility

圖片
Clash Royale CLAN TAG #URR8PPP up vote 0 down vote favorite Let $(W_s)_s geq 0$ be a Wiener process and $tau$ be a random variable with an exponential distribution with parameter $lambda$. Suppose that $W$ and $tau$ are independent. In this question, we see that the distribution of the stopped Wiener process $W_tau$ corresponds to a Laplace distribution with scale parameter $fracsigmasqrt2lambda$ where $sigma$ is the instantaneous variance of the Wiener process. Suppose now, that the variance $sigma^2$ also follows a stochastic process such that we have: $$dS = sigma SdW_s \ dsigma^2 = alphasigma^2dt + xisigma^2dW_sigma$$ where $alpha$ and $xi$ are independent of $S$ and $dW_s$ and $dW_sigma$ are independent Wiener processes. My aim is to derive the distribution of $log S_tau$. First, if $barV_T$ denotes the mean variance over some time interval $[0,T]$ defined by $$barV_T = frac1T intlimits_0^Tsigma^2(t)dt,$$ it is easy to show (Lemma of Îto) that $$...
閱讀完整內容