Need prove a Graphs with n >= 5 with a Euler path and without Hamilton Path and Hamilton Cycle exist.











up vote
1
down vote

favorite












I already proved a Euler Tour can't exist because all degrees would have to equal a number divisible by 2 but a Euler Path requires two odd degrees.



I still have to prove a graph exists that contains a Euler Path but doesn't contain a Hamilton Cycle/Path. I am new to Graph Theory which makes it really hard for me to think through the whole conditions existing there.










share|cite|improve this question


























    up vote
    1
    down vote

    favorite












    I already proved a Euler Tour can't exist because all degrees would have to equal a number divisible by 2 but a Euler Path requires two odd degrees.



    I still have to prove a graph exists that contains a Euler Path but doesn't contain a Hamilton Cycle/Path. I am new to Graph Theory which makes it really hard for me to think through the whole conditions existing there.










    share|cite|improve this question
























      up vote
      1
      down vote

      favorite









      up vote
      1
      down vote

      favorite











      I already proved a Euler Tour can't exist because all degrees would have to equal a number divisible by 2 but a Euler Path requires two odd degrees.



      I still have to prove a graph exists that contains a Euler Path but doesn't contain a Hamilton Cycle/Path. I am new to Graph Theory which makes it really hard for me to think through the whole conditions existing there.










      share|cite|improve this question













      I already proved a Euler Tour can't exist because all degrees would have to equal a number divisible by 2 but a Euler Path requires two odd degrees.



      I still have to prove a graph exists that contains a Euler Path but doesn't contain a Hamilton Cycle/Path. I am new to Graph Theory which makes it really hard for me to think through the whole conditions existing there.







      graph-theory hamiltonian-path path-connected eulerian-path






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Nov 14 at 22:21









      Xore

      61




      61






















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          1
          down vote













          It helps to be familiar with some extremal examples of non-Hamiltonian graphs, and reasons why a graph might fail to be Hamiltonian. I'm just going to go over a few of them here, though not all of them will help.



          For example, a graph might not be connected. That would do the job. It's not really useful here, though, because such a graph wouldn't have an Eulerian path either.



          A graph might fail to have a Hamiltonian cycle because it has a cut vertex, such as the graph below. If you start on the left, for instance, then to visit all the vertices you have to go through the middle vertex to get to the other side, and then go through it again to get back to where you started. It does have a Hamiltonian path, though, so it might not be the right tool for the job here.



          enter image description here



          An unbalanced bipartite graph, such as the one below, does not have a Hamiltonian cycle because any path or cycle alternates between one part and the other, and you run out of vertices on one side long before you run out of vertices on the other side. If the bipartite graph is sufficiently unbalanced, it does not have a Hamiltonian path, either. The particular example I drew below is not Eulerian, but you can find a counterexample of this form if you play with it a bit.



          enter image description here



          Finally, the Petersen graph is a graph with no Hamiltonian cycle that's a counter-example to about a billion different things. It doesn't help us here, because all its vertices are odd, but I'm going to mention it anyway because it's so useful so often.



          enter image description here






          share|cite|improve this answer





















            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: 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
            });


            }
            });














             

            draft saved


            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2998905%2fneed-prove-a-graphs-with-n-5-with-a-euler-path-and-without-hamilton-path-and%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








            up vote
            1
            down vote













            It helps to be familiar with some extremal examples of non-Hamiltonian graphs, and reasons why a graph might fail to be Hamiltonian. I'm just going to go over a few of them here, though not all of them will help.



            For example, a graph might not be connected. That would do the job. It's not really useful here, though, because such a graph wouldn't have an Eulerian path either.



            A graph might fail to have a Hamiltonian cycle because it has a cut vertex, such as the graph below. If you start on the left, for instance, then to visit all the vertices you have to go through the middle vertex to get to the other side, and then go through it again to get back to where you started. It does have a Hamiltonian path, though, so it might not be the right tool for the job here.



            enter image description here



            An unbalanced bipartite graph, such as the one below, does not have a Hamiltonian cycle because any path or cycle alternates between one part and the other, and you run out of vertices on one side long before you run out of vertices on the other side. If the bipartite graph is sufficiently unbalanced, it does not have a Hamiltonian path, either. The particular example I drew below is not Eulerian, but you can find a counterexample of this form if you play with it a bit.



            enter image description here



            Finally, the Petersen graph is a graph with no Hamiltonian cycle that's a counter-example to about a billion different things. It doesn't help us here, because all its vertices are odd, but I'm going to mention it anyway because it's so useful so often.



            enter image description here






            share|cite|improve this answer

























              up vote
              1
              down vote













              It helps to be familiar with some extremal examples of non-Hamiltonian graphs, and reasons why a graph might fail to be Hamiltonian. I'm just going to go over a few of them here, though not all of them will help.



              For example, a graph might not be connected. That would do the job. It's not really useful here, though, because such a graph wouldn't have an Eulerian path either.



              A graph might fail to have a Hamiltonian cycle because it has a cut vertex, such as the graph below. If you start on the left, for instance, then to visit all the vertices you have to go through the middle vertex to get to the other side, and then go through it again to get back to where you started. It does have a Hamiltonian path, though, so it might not be the right tool for the job here.



              enter image description here



              An unbalanced bipartite graph, such as the one below, does not have a Hamiltonian cycle because any path or cycle alternates between one part and the other, and you run out of vertices on one side long before you run out of vertices on the other side. If the bipartite graph is sufficiently unbalanced, it does not have a Hamiltonian path, either. The particular example I drew below is not Eulerian, but you can find a counterexample of this form if you play with it a bit.



              enter image description here



              Finally, the Petersen graph is a graph with no Hamiltonian cycle that's a counter-example to about a billion different things. It doesn't help us here, because all its vertices are odd, but I'm going to mention it anyway because it's so useful so often.



              enter image description here






              share|cite|improve this answer























                up vote
                1
                down vote










                up vote
                1
                down vote









                It helps to be familiar with some extremal examples of non-Hamiltonian graphs, and reasons why a graph might fail to be Hamiltonian. I'm just going to go over a few of them here, though not all of them will help.



                For example, a graph might not be connected. That would do the job. It's not really useful here, though, because such a graph wouldn't have an Eulerian path either.



                A graph might fail to have a Hamiltonian cycle because it has a cut vertex, such as the graph below. If you start on the left, for instance, then to visit all the vertices you have to go through the middle vertex to get to the other side, and then go through it again to get back to where you started. It does have a Hamiltonian path, though, so it might not be the right tool for the job here.



                enter image description here



                An unbalanced bipartite graph, such as the one below, does not have a Hamiltonian cycle because any path or cycle alternates between one part and the other, and you run out of vertices on one side long before you run out of vertices on the other side. If the bipartite graph is sufficiently unbalanced, it does not have a Hamiltonian path, either. The particular example I drew below is not Eulerian, but you can find a counterexample of this form if you play with it a bit.



                enter image description here



                Finally, the Petersen graph is a graph with no Hamiltonian cycle that's a counter-example to about a billion different things. It doesn't help us here, because all its vertices are odd, but I'm going to mention it anyway because it's so useful so often.



                enter image description here






                share|cite|improve this answer












                It helps to be familiar with some extremal examples of non-Hamiltonian graphs, and reasons why a graph might fail to be Hamiltonian. I'm just going to go over a few of them here, though not all of them will help.



                For example, a graph might not be connected. That would do the job. It's not really useful here, though, because such a graph wouldn't have an Eulerian path either.



                A graph might fail to have a Hamiltonian cycle because it has a cut vertex, such as the graph below. If you start on the left, for instance, then to visit all the vertices you have to go through the middle vertex to get to the other side, and then go through it again to get back to where you started. It does have a Hamiltonian path, though, so it might not be the right tool for the job here.



                enter image description here



                An unbalanced bipartite graph, such as the one below, does not have a Hamiltonian cycle because any path or cycle alternates between one part and the other, and you run out of vertices on one side long before you run out of vertices on the other side. If the bipartite graph is sufficiently unbalanced, it does not have a Hamiltonian path, either. The particular example I drew below is not Eulerian, but you can find a counterexample of this form if you play with it a bit.



                enter image description here



                Finally, the Petersen graph is a graph with no Hamiltonian cycle that's a counter-example to about a billion different things. It doesn't help us here, because all its vertices are odd, but I'm going to mention it anyway because it's so useful so often.



                enter image description here







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Nov 15 at 2:56









                Misha Lavrov

                41.6k555101




                41.6k555101






























                     

                    draft saved


                    draft discarded



















































                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2998905%2fneed-prove-a-graphs-with-n-5-with-a-euler-path-and-without-hamilton-path-and%23new-answer', 'question_page');
                    }
                    );

                    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







                    Popular posts from this blog

                    Probability when a professor distributes a quiz and homework assignment to a class of n students.

                    Aardman Animations

                    Are they similar matrix