3 ms·

Sure. Prove that a Peterson graph can’t have a Hamiltonian cycle. Often given as a paragraph of English. Actually I’ve only seen it that way personally. Of cou

Sure. Prove that a Peterson graph can’t have a Hamiltonian cycle. Often given as a paragraph of English. Actually I’ve only seen it that way personally. Of course you could (in this example) prove it deductively since Peterson graphs have a specific size , or inductively otherwise but you’d first need to establish a framework... and not a “intuitive framework” at that. Well, all you’ve got then is something axiomatic in which case we arrive back at “intuition” for you axioms. Here’s a whole line of argument about a large part of the proof we know: https://en.m.wikipedia.org/wiki/Constructive_proof https://en.m.wikipedia.org/wiki/Constructive_proof

tome 8y ago
I guess you're talking about the paragraph in this section: https://en.wikipedia.org/wiki/Petersen_graph#Hamiltonian_paths_and_cycles https://en.wikipedia.org/wiki/Petersen_graph#Hamiltonian_pat... I'm not sure what you mean by "intuition". Do you doubt that this proof has a straightforward translation into formal language?
- mgsouth 8y ago
  I think the point is that it usually isn't given formally. In practice it's just too tedious to formally specify proofs using some kind of rigorous set-theoretic language. It's like building a web app with a Turing machine.
  - tome 8y ago
    > I think the point is that it usually isn't given formally. Is the claim that the opposite of "formal" is "intuitive"? That's news to me!
    - usgroup 8y ago
      I think your statement sounds controversial but I’d be willing to argue that. I.e the opposite of formal is indeed intuitive. I’d start like this : if you’re explaining something in English then you’re invoking and reliant on the readers common sense and intuition to do the work in your explanation. E.g a pipe is used to smoke tobacco. Pipe. Usage. Smoking. Tobacco. It’s left to the reader to define, disambiguate and on that basis accept. Contrast to: a pipe is used for transporting water.
- usgroup 8y ago
  My point is formal language doesn’t mean “doesn’t require intuition”. By “intuition” I mean the appeal to something you expect the reader to believe without further proof. I hadn’t seen the Wikipedia article you point out but Peterson graphs will be in many graph theory textbooks. Again have a look at the article on constructionist proof for another angle on maths and intuition.
  - n4r9 8y ago
    > Peterson graphs The plural here is confusing. Are you talking about the Petersen graph, on ten vertices? There does exist a constructivist proof of its non-Hamiltonicity: merely enumerate every cycle of length ten and show that none are Hamiltonian. There is a class of objects called generalised Petersen graphs but these are usually Hamiltonian: https://core.ac.uk/download/pdf/82084439.pdf https://core.ac.uk/download/pdf/82084439.pdf

tome 8y ago

I guess you're talking about the paragraph in this section: https://en.wikipedia.org/wiki/Petersen_graph#Hamiltonian_paths_and_cycles https://en.wikipedia.org/wiki/Petersen_graph#Hamiltonian_pat... I'm not sure what you mean by "intuition". Do you doubt that this proof has a straightforward translation into formal language?

mgsouth 8y ago
I think the point is that it usually isn't given formally. In practice it's just too tedious to formally specify proofs using some kind of rigorous set-theoretic language. It's like building a web app with a Turing machine.
- tome 8y ago
  > I think the point is that it usually isn't given formally. Is the claim that the opposite of "formal" is "intuitive"? That's news to me!
  - usgroup 8y ago
    I think your statement sounds controversial but I’d be willing to argue that. I.e the opposite of formal is indeed intuitive. I’d start like this : if you’re explaining something in English then you’re invoking and reliant on the readers common sense and intuition to do the work in your explanation. E.g a pipe is used to smoke tobacco. Pipe. Usage. Smoking. Tobacco. It’s left to the reader to define, disambiguate and on that basis accept. Contrast to: a pipe is used for transporting water.
usgroup 8y ago
My point is formal language doesn’t mean “doesn’t require intuition”. By “intuition” I mean the appeal to something you expect the reader to believe without further proof. I hadn’t seen the Wikipedia article you point out but Peterson graphs will be in many graph theory textbooks. Again have a look at the article on constructionist proof for another angle on maths and intuition.
- n4r9 8y ago
  > Peterson graphs The plural here is confusing. Are you talking about the Petersen graph, on ten vertices? There does exist a constructivist proof of its non-Hamiltonicity: merely enumerate every cycle of length ten and show that none are Hamiltonian. There is a class of objects called generalised Petersen graphs but these are usually Hamiltonian: https://core.ac.uk/download/pdf/82084439.pdf https://core.ac.uk/download/pdf/82084439.pdf