Edges on an even number of Hamilton cycles












1












$begingroup$


Let $G$ be a graph in which every vertex has odd degree. Show that every edge of $G$ lies on an even number of Hamilton cycles.






graph-theory







share|cite|improve this question











$endgroup$












  • $begingroup$
    See mathworld.wolfram.com/SmithsNetworkTheorem.html.
    $endgroup$
    – domotorp
    Sep 28 '16 at 7:13
















1












$begingroup$


Let $G$ be a graph in which every vertex has odd degree. Show that every edge of $G$ lies on an even number of Hamilton cycles.






graph-theory







share|cite|improve this question











$endgroup$












  • $begingroup$
    See mathworld.wolfram.com/SmithsNetworkTheorem.html.
    $endgroup$
    – domotorp
    Sep 28 '16 at 7:13














1












1








1


2



$begingroup$


Let $G$ be a graph in which every vertex has odd degree. Show that every edge of $G$ lies on an even number of Hamilton cycles.






graph-theory







share|cite|improve this question











$endgroup$




Let $G$ be a graph in which every vertex has odd degree. Show that every edge of $G$ lies on an even number of Hamilton cycles.






graph-theory




graph-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Feb 23 '13 at 21:03









MJD

47.1k29209392




47.1k29209392










asked Jan 27 '13 at 3:28









Andrés Felipe Téllez CrespoAndrés Felipe Téllez Crespo

1628




1628












  • $begingroup$
    See mathworld.wolfram.com/SmithsNetworkTheorem.html.
    $endgroup$
    – domotorp
    Sep 28 '16 at 7:13


















  • $begingroup$
    See mathworld.wolfram.com/SmithsNetworkTheorem.html.
    $endgroup$
    – domotorp
    Sep 28 '16 at 7:13
















$begingroup$
See mathworld.wolfram.com/SmithsNetworkTheorem.html.
$endgroup$
– domotorp
Sep 28 '16 at 7:13




$begingroup$
See mathworld.wolfram.com/SmithsNetworkTheorem.html.
$endgroup$
– domotorp
Sep 28 '16 at 7:13










1 Answer
1






active

oldest

votes


















8












$begingroup$

Let $e={u,v_0}$ be an edge in the graph $G$, whose vertices all have odd degree. Let $P$ be the set of Hamilton paths that begin $u,e,v_0$; $P$ will be the vertex set of a new graph $H$. Suppose that $pin P$ is $u,e,v_0,e_0,v_1,dots,e_{n-1},v_n$. If ${v_n,v_k}$ is an edge for some $k<n-1$ we can remove the edge $e_k={v_k,v_{k+1}}$ and add the edge $e'={v_n,v_k}$ to get $$q=u,e,v,e_0,v_1,dots,v_k,e',v_n,e_{n-1},v_{n-1},dots,v_{k+1};,$$ another path in $P$. Note that $p$ can be obtained from $q$ by a similar operation. If $p_1,p_2in P$, ${p_1,p_2}$ is an edge of $H$ iff each can be obtained from the other as $q$ was obtained from $p$.



Fix $pin P$ as above. Then $deg_H(p)$ is just the number of edges ${v_n,v_k}$ with $k<n-1$. This accounts for every edge of $G$ incident at $v_n$ except $e_{n-1}={v_{n-1},v_n}$ and possibly ${v_n,u}$. If ${v_n,u}$ is an edge of $G$, then $p$ is part of a Hamilton cycle through $e$, and $deg_H(p)=deg_G(v_n)-2$, which is odd; otherwise, $p$ is not part of a Hamilton cycle through $e$, and $deg_H(p)=deg_G(v_n)-1$, which is even. $H$ must have an even number of odd vertices, so $G$ must have an even number of Hamilton cycles through the edge $e$.






share|cite|improve this answer











$endgroup$













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


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f287856%2fedges-on-an-even-number-of-hamilton-cycles%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









    8












    $begingroup$

    Let $e={u,v_0}$ be an edge in the graph $G$, whose vertices all have odd degree. Let $P$ be the set of Hamilton paths that begin $u,e,v_0$; $P$ will be the vertex set of a new graph $H$. Suppose that $pin P$ is $u,e,v_0,e_0,v_1,dots,e_{n-1},v_n$. If ${v_n,v_k}$ is an edge for some $k<n-1$ we can remove the edge $e_k={v_k,v_{k+1}}$ and add the edge $e'={v_n,v_k}$ to get $$q=u,e,v,e_0,v_1,dots,v_k,e',v_n,e_{n-1},v_{n-1},dots,v_{k+1};,$$ another path in $P$. Note that $p$ can be obtained from $q$ by a similar operation. If $p_1,p_2in P$, ${p_1,p_2}$ is an edge of $H$ iff each can be obtained from the other as $q$ was obtained from $p$.



    Fix $pin P$ as above. Then $deg_H(p)$ is just the number of edges ${v_n,v_k}$ with $k<n-1$. This accounts for every edge of $G$ incident at $v_n$ except $e_{n-1}={v_{n-1},v_n}$ and possibly ${v_n,u}$. If ${v_n,u}$ is an edge of $G$, then $p$ is part of a Hamilton cycle through $e$, and $deg_H(p)=deg_G(v_n)-2$, which is odd; otherwise, $p$ is not part of a Hamilton cycle through $e$, and $deg_H(p)=deg_G(v_n)-1$, which is even. $H$ must have an even number of odd vertices, so $G$ must have an even number of Hamilton cycles through the edge $e$.






    share|cite|improve this answer











    $endgroup$


















      8












      $begingroup$

      Let $e={u,v_0}$ be an edge in the graph $G$, whose vertices all have odd degree. Let $P$ be the set of Hamilton paths that begin $u,e,v_0$; $P$ will be the vertex set of a new graph $H$. Suppose that $pin P$ is $u,e,v_0,e_0,v_1,dots,e_{n-1},v_n$. If ${v_n,v_k}$ is an edge for some $k<n-1$ we can remove the edge $e_k={v_k,v_{k+1}}$ and add the edge $e'={v_n,v_k}$ to get $$q=u,e,v,e_0,v_1,dots,v_k,e',v_n,e_{n-1},v_{n-1},dots,v_{k+1};,$$ another path in $P$. Note that $p$ can be obtained from $q$ by a similar operation. If $p_1,p_2in P$, ${p_1,p_2}$ is an edge of $H$ iff each can be obtained from the other as $q$ was obtained from $p$.



      Fix $pin P$ as above. Then $deg_H(p)$ is just the number of edges ${v_n,v_k}$ with $k<n-1$. This accounts for every edge of $G$ incident at $v_n$ except $e_{n-1}={v_{n-1},v_n}$ and possibly ${v_n,u}$. If ${v_n,u}$ is an edge of $G$, then $p$ is part of a Hamilton cycle through $e$, and $deg_H(p)=deg_G(v_n)-2$, which is odd; otherwise, $p$ is not part of a Hamilton cycle through $e$, and $deg_H(p)=deg_G(v_n)-1$, which is even. $H$ must have an even number of odd vertices, so $G$ must have an even number of Hamilton cycles through the edge $e$.






      share|cite|improve this answer











      $endgroup$
















        8












        8








        8





        $begingroup$

        Let $e={u,v_0}$ be an edge in the graph $G$, whose vertices all have odd degree. Let $P$ be the set of Hamilton paths that begin $u,e,v_0$; $P$ will be the vertex set of a new graph $H$. Suppose that $pin P$ is $u,e,v_0,e_0,v_1,dots,e_{n-1},v_n$. If ${v_n,v_k}$ is an edge for some $k<n-1$ we can remove the edge $e_k={v_k,v_{k+1}}$ and add the edge $e'={v_n,v_k}$ to get $$q=u,e,v,e_0,v_1,dots,v_k,e',v_n,e_{n-1},v_{n-1},dots,v_{k+1};,$$ another path in $P$. Note that $p$ can be obtained from $q$ by a similar operation. If $p_1,p_2in P$, ${p_1,p_2}$ is an edge of $H$ iff each can be obtained from the other as $q$ was obtained from $p$.



        Fix $pin P$ as above. Then $deg_H(p)$ is just the number of edges ${v_n,v_k}$ with $k<n-1$. This accounts for every edge of $G$ incident at $v_n$ except $e_{n-1}={v_{n-1},v_n}$ and possibly ${v_n,u}$. If ${v_n,u}$ is an edge of $G$, then $p$ is part of a Hamilton cycle through $e$, and $deg_H(p)=deg_G(v_n)-2$, which is odd; otherwise, $p$ is not part of a Hamilton cycle through $e$, and $deg_H(p)=deg_G(v_n)-1$, which is even. $H$ must have an even number of odd vertices, so $G$ must have an even number of Hamilton cycles through the edge $e$.






        share|cite|improve this answer











        $endgroup$



        Let $e={u,v_0}$ be an edge in the graph $G$, whose vertices all have odd degree. Let $P$ be the set of Hamilton paths that begin $u,e,v_0$; $P$ will be the vertex set of a new graph $H$. Suppose that $pin P$ is $u,e,v_0,e_0,v_1,dots,e_{n-1},v_n$. If ${v_n,v_k}$ is an edge for some $k<n-1$ we can remove the edge $e_k={v_k,v_{k+1}}$ and add the edge $e'={v_n,v_k}$ to get $$q=u,e,v,e_0,v_1,dots,v_k,e',v_n,e_{n-1},v_{n-1},dots,v_{k+1};,$$ another path in $P$. Note that $p$ can be obtained from $q$ by a similar operation. If $p_1,p_2in P$, ${p_1,p_2}$ is an edge of $H$ iff each can be obtained from the other as $q$ was obtained from $p$.



        Fix $pin P$ as above. Then $deg_H(p)$ is just the number of edges ${v_n,v_k}$ with $k<n-1$. This accounts for every edge of $G$ incident at $v_n$ except $e_{n-1}={v_{n-1},v_n}$ and possibly ${v_n,u}$. If ${v_n,u}$ is an edge of $G$, then $p$ is part of a Hamilton cycle through $e$, and $deg_H(p)=deg_G(v_n)-2$, which is odd; otherwise, $p$ is not part of a Hamilton cycle through $e$, and $deg_H(p)=deg_G(v_n)-1$, which is even. $H$ must have an even number of odd vertices, so $G$ must have an even number of Hamilton cycles through the edge $e$.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Jan 27 '13 at 22:45

























        answered Jan 27 '13 at 5:47









        Brian M. ScottBrian M. Scott

        456k38507908




        456k38507908






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f287856%2fedges-on-an-even-number-of-hamilton-cycles%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

            Eda skans

            Image
            .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
            Read more

            William S. Burroughs

            Image
            William S. Burroughs From Wikipedia, the free encyclopedia   (Redirected from William Burroughs) Jump to navigation Jump to search For other people named William Burroughs, see William Burroughs (disambiguation). William S. Burroughs Burroughs in 1983 Born William Seward Burroughs II ( 1914-02-05 ) February 5, 1914 St. Louis, Missouri, United States Died August 2, 1997 (1997-08-02) (aged 83) Lawrence, Kansas, United States Pen name William Lee Occupation Author Alma mater Harvard University Genre Beat literature, paranoid fiction Literary movement Beat Generation, postmodernism Notable works Naked Lunch (1959), Junkie (1953) Spouse Ilse von Klapper (1937–1946) Joan Vollmer (1946–1951) Children William S. Burroughs Jr. Relatives William Seward Burroughs I, grandfather Ivy Lee, maternal uncle Signature William Seward Burroughs II ( / ˈ b ʌr oʊ z / ; February...
            Read more

            What is the difference between apt, apt-get and git?

            Image
            1 I use Xubuntu and found that I can update packages by using apt and apt-get . But I have heard that programmers use usually git in their project to manage different version. So why Xubuntu do not use git to handle different versions of software? apt software-installation git version-control share | improve this question edited Jan 14 at 18:51 Rui F Ribeiro 39.5k 14 79 132 asked Jan 14 at 18:43 Verybeginner Verybeginner 17 2 ...
            Read more