Components of graph with edges given by congruence condition












3














Let $G_n = (V_n, E_n)$ denote the graph with vertex set $V_n = {0, 1, 2, dotsc, n – 1}$ and edge set $E_n = left{{i, j}: i + j equiv 1 pmod{n}right}$ where $n ge 3$. How many components does $G_n$ have for $n ge 3$?



The answer is $lceil n/2 rceil$ if we allow loops. I've gotten the answer by making graphs for different values of $n$. Can anyone help with a constructive proof?






combinatorics graph-theory







share|cite|improve this question
























  • If you've been constructing the graphs by hand, you should see a pattern. What's the pattern you see?
    – Mike Pierce
    Nov 29 '16 at 3:16










  • Sir +Mike, Thanks for you comment. What I see is - this question is reduced to the combinatorial problem of finding number of combination (x,y) = n+1.
    – Mr.Sigma.
    Nov 29 '16 at 4:04










  • Basically, yeah, ... and what's the pattern you see when drawing the graphs? What led you to conclude that the answer should be $lceil n/2 rceil$?
    – Mike Pierce
    Nov 29 '16 at 4:07












  • Sir +Mike, I've just tried with n=3,4,5 & got the answer. But the pattern I see somewhat is like (n/2,n/2+1), (n/2-1,n/2+2),(n/2-2,n/2+3) ... Am I correct? Apart from trivial (0,1) edge.
    – Mr.Sigma.
    Nov 29 '16 at 4:10












  • Thanks Sir +Mike for helping me, I got it counting terms of this series alone. :)
    – Mr.Sigma.
    Nov 29 '16 at 4:19
















3














Let $G_n = (V_n, E_n)$ denote the graph with vertex set $V_n = {0, 1, 2, dotsc, n – 1}$ and edge set $E_n = left{{i, j}: i + j equiv 1 pmod{n}right}$ where $n ge 3$. How many components does $G_n$ have for $n ge 3$?



The answer is $lceil n/2 rceil$ if we allow loops. I've gotten the answer by making graphs for different values of $n$. Can anyone help with a constructive proof?






combinatorics graph-theory







share|cite|improve this question
























  • If you've been constructing the graphs by hand, you should see a pattern. What's the pattern you see?
    – Mike Pierce
    Nov 29 '16 at 3:16










  • Sir +Mike, Thanks for you comment. What I see is - this question is reduced to the combinatorial problem of finding number of combination (x,y) = n+1.
    – Mr.Sigma.
    Nov 29 '16 at 4:04










  • Basically, yeah, ... and what's the pattern you see when drawing the graphs? What led you to conclude that the answer should be $lceil n/2 rceil$?
    – Mike Pierce
    Nov 29 '16 at 4:07












  • Sir +Mike, I've just tried with n=3,4,5 & got the answer. But the pattern I see somewhat is like (n/2,n/2+1), (n/2-1,n/2+2),(n/2-2,n/2+3) ... Am I correct? Apart from trivial (0,1) edge.
    – Mr.Sigma.
    Nov 29 '16 at 4:10












  • Thanks Sir +Mike for helping me, I got it counting terms of this series alone. :)
    – Mr.Sigma.
    Nov 29 '16 at 4:19














3












3








3







Let $G_n = (V_n, E_n)$ denote the graph with vertex set $V_n = {0, 1, 2, dotsc, n – 1}$ and edge set $E_n = left{{i, j}: i + j equiv 1 pmod{n}right}$ where $n ge 3$. How many components does $G_n$ have for $n ge 3$?



The answer is $lceil n/2 rceil$ if we allow loops. I've gotten the answer by making graphs for different values of $n$. Can anyone help with a constructive proof?






combinatorics graph-theory







share|cite|improve this question















Let $G_n = (V_n, E_n)$ denote the graph with vertex set $V_n = {0, 1, 2, dotsc, n – 1}$ and edge set $E_n = left{{i, j}: i + j equiv 1 pmod{n}right}$ where $n ge 3$. How many components does $G_n$ have for $n ge 3$?



The answer is $lceil n/2 rceil$ if we allow loops. I've gotten the answer by making graphs for different values of $n$. Can anyone help with a constructive proof?






combinatorics graph-theory




combinatorics graph-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 29 '16 at 6:21









Gerry Myerson

146k8147298




146k8147298










asked Nov 29 '16 at 3:04









Mr.Sigma.Mr.Sigma.

1719




1719












  • If you've been constructing the graphs by hand, you should see a pattern. What's the pattern you see?
    – Mike Pierce
    Nov 29 '16 at 3:16










  • Sir +Mike, Thanks for you comment. What I see is - this question is reduced to the combinatorial problem of finding number of combination (x,y) = n+1.
    – Mr.Sigma.
    Nov 29 '16 at 4:04










  • Basically, yeah, ... and what's the pattern you see when drawing the graphs? What led you to conclude that the answer should be $lceil n/2 rceil$?
    – Mike Pierce
    Nov 29 '16 at 4:07












  • Sir +Mike, I've just tried with n=3,4,5 & got the answer. But the pattern I see somewhat is like (n/2,n/2+1), (n/2-1,n/2+2),(n/2-2,n/2+3) ... Am I correct? Apart from trivial (0,1) edge.
    – Mr.Sigma.
    Nov 29 '16 at 4:10












  • Thanks Sir +Mike for helping me, I got it counting terms of this series alone. :)
    – Mr.Sigma.
    Nov 29 '16 at 4:19


















  • If you've been constructing the graphs by hand, you should see a pattern. What's the pattern you see?
    – Mike Pierce
    Nov 29 '16 at 3:16










  • Sir +Mike, Thanks for you comment. What I see is - this question is reduced to the combinatorial problem of finding number of combination (x,y) = n+1.
    – Mr.Sigma.
    Nov 29 '16 at 4:04










  • Basically, yeah, ... and what's the pattern you see when drawing the graphs? What led you to conclude that the answer should be $lceil n/2 rceil$?
    – Mike Pierce
    Nov 29 '16 at 4:07












  • Sir +Mike, I've just tried with n=3,4,5 & got the answer. But the pattern I see somewhat is like (n/2,n/2+1), (n/2-1,n/2+2),(n/2-2,n/2+3) ... Am I correct? Apart from trivial (0,1) edge.
    – Mr.Sigma.
    Nov 29 '16 at 4:10












  • Thanks Sir +Mike for helping me, I got it counting terms of this series alone. :)
    – Mr.Sigma.
    Nov 29 '16 at 4:19
















If you've been constructing the graphs by hand, you should see a pattern. What's the pattern you see?
– Mike Pierce
Nov 29 '16 at 3:16




If you've been constructing the graphs by hand, you should see a pattern. What's the pattern you see?
– Mike Pierce
Nov 29 '16 at 3:16












Sir +Mike, Thanks for you comment. What I see is - this question is reduced to the combinatorial problem of finding number of combination (x,y) = n+1.
– Mr.Sigma.
Nov 29 '16 at 4:04




Sir +Mike, Thanks for you comment. What I see is - this question is reduced to the combinatorial problem of finding number of combination (x,y) = n+1.
– Mr.Sigma.
Nov 29 '16 at 4:04












Basically, yeah, ... and what's the pattern you see when drawing the graphs? What led you to conclude that the answer should be $lceil n/2 rceil$?
– Mike Pierce
Nov 29 '16 at 4:07






Basically, yeah, ... and what's the pattern you see when drawing the graphs? What led you to conclude that the answer should be $lceil n/2 rceil$?
– Mike Pierce
Nov 29 '16 at 4:07














Sir +Mike, I've just tried with n=3,4,5 & got the answer. But the pattern I see somewhat is like (n/2,n/2+1), (n/2-1,n/2+2),(n/2-2,n/2+3) ... Am I correct? Apart from trivial (0,1) edge.
– Mr.Sigma.
Nov 29 '16 at 4:10






Sir +Mike, I've just tried with n=3,4,5 & got the answer. But the pattern I see somewhat is like (n/2,n/2+1), (n/2-1,n/2+2),(n/2-2,n/2+3) ... Am I correct? Apart from trivial (0,1) edge.
– Mr.Sigma.
Nov 29 '16 at 4:10














Thanks Sir +Mike for helping me, I got it counting terms of this series alone. :)
– Mr.Sigma.
Nov 29 '16 at 4:19




Thanks Sir +Mike for helping me, I got it counting terms of this series alone. :)
– Mr.Sigma.
Nov 29 '16 at 4:19










2 Answers
2






active

oldest

votes


















1














Since we are working $bmod n$, I think it would be easier to name the vertices ${1, dotsc, n}$ instead; the problem is the same. We see pretty quickly by playing around that the edges



$$(1,n)quad(2,n!-!1)quaddotsbquadleft(lfloor n/2rfloor, 1+lfloor n/2rfloorright)$$



must be in our graph. So there are at most $lceil n/2 rceil$ connected components, each component having one edge except for a single component with an isolated vertex if $n$ is odd. This is also all the components. On the contrary if we suppose that our graph has some edges $(a,b)$ and $(b,c)$ for distinct vertices $a$ and $c$, we would have



$$a+b equiv 1 quadtext{and}quad b+c equiv 1;.$$



Subtracting these two congruence we get that $aequiv c pmod n$. But since our vertices are just ${1,dotsc,n}$ this is only possible if $a=c$.






share|cite|improve this answer





























    1














    Here is how I solved the problem.



    Since sum would be $n+1$. Patterns of edges would be like this:



    $(lfloor{(n/2)}rfloor, lfloor{(n/2)}rfloor +1), (lfloor{(n/2)}rfloor-1, lfloor{(n/2)}rfloor +2),...,(2,lfloor{(n/2)}rfloor+lfloor{(n/2)}rfloor
    -1)$



    Therefore total pairs $= lfloor{(n/2)}rfloor -1 -1+1 = lfloor{(n/2)}rfloor -1$



    Considering trivial $(0,1)$ Total pairs or edges are $= lfloor{(n/2)}rfloor$. 



    Now, with $n$ vertices & $k$ components a forest has $n-k$ edges. 



    $implies n - k = lfloor{(n/2)}rfloor$



    $implies k = n - lfloor{(n/2)}rfloor =
    lceil{(n/2)}rceil$






    share|cite|improve this answer



















    • 1




      You should check out this guide on how to nicely typeset mathematics on this site.
      – Mike Pierce
      Nov 29 '16 at 6:15










    • 😷😷😷😂😂😂 Will try sir.
      – Mr.Sigma.
      Nov 29 '16 at 6:19











    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%2f2035269%2fcomponents-of-graph-with-edges-given-by-congruence-condition%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1














    Since we are working $bmod n$, I think it would be easier to name the vertices ${1, dotsc, n}$ instead; the problem is the same. We see pretty quickly by playing around that the edges



    $$(1,n)quad(2,n!-!1)quaddotsbquadleft(lfloor n/2rfloor, 1+lfloor n/2rfloorright)$$



    must be in our graph. So there are at most $lceil n/2 rceil$ connected components, each component having one edge except for a single component with an isolated vertex if $n$ is odd. This is also all the components. On the contrary if we suppose that our graph has some edges $(a,b)$ and $(b,c)$ for distinct vertices $a$ and $c$, we would have



    $$a+b equiv 1 quadtext{and}quad b+c equiv 1;.$$



    Subtracting these two congruence we get that $aequiv c pmod n$. But since our vertices are just ${1,dotsc,n}$ this is only possible if $a=c$.






    share|cite|improve this answer


























      1














      Since we are working $bmod n$, I think it would be easier to name the vertices ${1, dotsc, n}$ instead; the problem is the same. We see pretty quickly by playing around that the edges



      $$(1,n)quad(2,n!-!1)quaddotsbquadleft(lfloor n/2rfloor, 1+lfloor n/2rfloorright)$$



      must be in our graph. So there are at most $lceil n/2 rceil$ connected components, each component having one edge except for a single component with an isolated vertex if $n$ is odd. This is also all the components. On the contrary if we suppose that our graph has some edges $(a,b)$ and $(b,c)$ for distinct vertices $a$ and $c$, we would have



      $$a+b equiv 1 quadtext{and}quad b+c equiv 1;.$$



      Subtracting these two congruence we get that $aequiv c pmod n$. But since our vertices are just ${1,dotsc,n}$ this is only possible if $a=c$.






      share|cite|improve this answer
























        1












        1








        1






        Since we are working $bmod n$, I think it would be easier to name the vertices ${1, dotsc, n}$ instead; the problem is the same. We see pretty quickly by playing around that the edges



        $$(1,n)quad(2,n!-!1)quaddotsbquadleft(lfloor n/2rfloor, 1+lfloor n/2rfloorright)$$



        must be in our graph. So there are at most $lceil n/2 rceil$ connected components, each component having one edge except for a single component with an isolated vertex if $n$ is odd. This is also all the components. On the contrary if we suppose that our graph has some edges $(a,b)$ and $(b,c)$ for distinct vertices $a$ and $c$, we would have



        $$a+b equiv 1 quadtext{and}quad b+c equiv 1;.$$



        Subtracting these two congruence we get that $aequiv c pmod n$. But since our vertices are just ${1,dotsc,n}$ this is only possible if $a=c$.






        share|cite|improve this answer












        Since we are working $bmod n$, I think it would be easier to name the vertices ${1, dotsc, n}$ instead; the problem is the same. We see pretty quickly by playing around that the edges



        $$(1,n)quad(2,n!-!1)quaddotsbquadleft(lfloor n/2rfloor, 1+lfloor n/2rfloorright)$$



        must be in our graph. So there are at most $lceil n/2 rceil$ connected components, each component having one edge except for a single component with an isolated vertex if $n$ is odd. This is also all the components. On the contrary if we suppose that our graph has some edges $(a,b)$ and $(b,c)$ for distinct vertices $a$ and $c$, we would have



        $$a+b equiv 1 quadtext{and}quad b+c equiv 1;.$$



        Subtracting these two congruence we get that $aequiv c pmod n$. But since our vertices are just ${1,dotsc,n}$ this is only possible if $a=c$.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Nov 30 '16 at 1:15









        Mike PierceMike Pierce

        11.4k103583




        11.4k103583























            1














            Here is how I solved the problem.



            Since sum would be $n+1$. Patterns of edges would be like this:



            $(lfloor{(n/2)}rfloor, lfloor{(n/2)}rfloor +1), (lfloor{(n/2)}rfloor-1, lfloor{(n/2)}rfloor +2),...,(2,lfloor{(n/2)}rfloor+lfloor{(n/2)}rfloor
            -1)$



            Therefore total pairs $= lfloor{(n/2)}rfloor -1 -1+1 = lfloor{(n/2)}rfloor -1$



            Considering trivial $(0,1)$ Total pairs or edges are $= lfloor{(n/2)}rfloor$. 



            Now, with $n$ vertices & $k$ components a forest has $n-k$ edges. 



            $implies n - k = lfloor{(n/2)}rfloor$



            $implies k = n - lfloor{(n/2)}rfloor =
            lceil{(n/2)}rceil$






            share|cite|improve this answer



















            • 1




              You should check out this guide on how to nicely typeset mathematics on this site.
              – Mike Pierce
              Nov 29 '16 at 6:15










            • 😷😷😷😂😂😂 Will try sir.
              – Mr.Sigma.
              Nov 29 '16 at 6:19
















            1














            Here is how I solved the problem.



            Since sum would be $n+1$. Patterns of edges would be like this:



            $(lfloor{(n/2)}rfloor, lfloor{(n/2)}rfloor +1), (lfloor{(n/2)}rfloor-1, lfloor{(n/2)}rfloor +2),...,(2,lfloor{(n/2)}rfloor+lfloor{(n/2)}rfloor
            -1)$



            Therefore total pairs $= lfloor{(n/2)}rfloor -1 -1+1 = lfloor{(n/2)}rfloor -1$



            Considering trivial $(0,1)$ Total pairs or edges are $= lfloor{(n/2)}rfloor$. 



            Now, with $n$ vertices & $k$ components a forest has $n-k$ edges. 



            $implies n - k = lfloor{(n/2)}rfloor$



            $implies k = n - lfloor{(n/2)}rfloor =
            lceil{(n/2)}rceil$






            share|cite|improve this answer



















            • 1




              You should check out this guide on how to nicely typeset mathematics on this site.
              – Mike Pierce
              Nov 29 '16 at 6:15










            • 😷😷😷😂😂😂 Will try sir.
              – Mr.Sigma.
              Nov 29 '16 at 6:19














            1












            1








            1






            Here is how I solved the problem.



            Since sum would be $n+1$. Patterns of edges would be like this:



            $(lfloor{(n/2)}rfloor, lfloor{(n/2)}rfloor +1), (lfloor{(n/2)}rfloor-1, lfloor{(n/2)}rfloor +2),...,(2,lfloor{(n/2)}rfloor+lfloor{(n/2)}rfloor
            -1)$



            Therefore total pairs $= lfloor{(n/2)}rfloor -1 -1+1 = lfloor{(n/2)}rfloor -1$



            Considering trivial $(0,1)$ Total pairs or edges are $= lfloor{(n/2)}rfloor$. 



            Now, with $n$ vertices & $k$ components a forest has $n-k$ edges. 



            $implies n - k = lfloor{(n/2)}rfloor$



            $implies k = n - lfloor{(n/2)}rfloor =
            lceil{(n/2)}rceil$






            share|cite|improve this answer














            Here is how I solved the problem.



            Since sum would be $n+1$. Patterns of edges would be like this:



            $(lfloor{(n/2)}rfloor, lfloor{(n/2)}rfloor +1), (lfloor{(n/2)}rfloor-1, lfloor{(n/2)}rfloor +2),...,(2,lfloor{(n/2)}rfloor+lfloor{(n/2)}rfloor
            -1)$



            Therefore total pairs $= lfloor{(n/2)}rfloor -1 -1+1 = lfloor{(n/2)}rfloor -1$



            Considering trivial $(0,1)$ Total pairs or edges are $= lfloor{(n/2)}rfloor$. 



            Now, with $n$ vertices & $k$ components a forest has $n-k$ edges. 



            $implies n - k = lfloor{(n/2)}rfloor$



            $implies k = n - lfloor{(n/2)}rfloor =
            lceil{(n/2)}rceil$







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Dec 1 '18 at 5:34

























            answered Nov 29 '16 at 6:09









            Mr.Sigma.Mr.Sigma.

            1719




            1719








            • 1




              You should check out this guide on how to nicely typeset mathematics on this site.
              – Mike Pierce
              Nov 29 '16 at 6:15










            • 😷😷😷😂😂😂 Will try sir.
              – Mr.Sigma.
              Nov 29 '16 at 6:19














            • 1




              You should check out this guide on how to nicely typeset mathematics on this site.
              – Mike Pierce
              Nov 29 '16 at 6:15










            • 😷😷😷😂😂😂 Will try sir.
              – Mr.Sigma.
              Nov 29 '16 at 6:19








            1




            1




            You should check out this guide on how to nicely typeset mathematics on this site.
            – Mike Pierce
            Nov 29 '16 at 6:15




            You should check out this guide on how to nicely typeset mathematics on this site.
            – Mike Pierce
            Nov 29 '16 at 6:15












            😷😷😷😂😂😂 Will try sir.
            – Mr.Sigma.
            Nov 29 '16 at 6:19




            😷😷😷😂😂😂 Will try sir.
            – Mr.Sigma.
            Nov 29 '16 at 6:19


















            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%2f2035269%2fcomponents-of-graph-with-edges-given-by-congruence-condition%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.

            Image
            0 0 $begingroup$ Need help with this problem. Suppose our lazy professor collects a quiz and a homework assignment from a class of n students one day, then distributes both the quizzes and the homework assignments back to the class in a random fashion for grading. Each student receives one quiz and one homework assignment to grade. (a) What is the probability that every student receives someone else's quiz to grade, and someone else's homework to grade? (b) What is the probability that no student receives both their own quiz and their own homework assignment to grade? In this case, some students may receive their own quiz, and others may receive their own homework assignment. (c) Compute the limiting probability as n approaches infinity in each case. ...
            Read more

            Aardman Animations

            Image
            Aardman Animations, Ltd. Aardman Animations Tipo privada Atividade Animação em stop-motion , Animação em CGI Fundação 1972 Fundador(es) Peter Lord David Sproxton Sede Bristol, Inglaterra  Reino Unido Proprietário(s) Dreamworks Pessoas-chave Peter Lord David Sproxton Nick Park Divisões Aardman Features Aardman Digital Aardman Commercials Aardman Broadcast Aardman International Aardman Rights Aardman Effects Aardman 3-D Systems Aardman Nathan Love AardBoiled Website oficial aardman.com ...
            Read more

            Are they similar matrix

            Image
            0 $begingroup$ Do $begin{bmatrix} 0&i&0\0&0&1\0&0&0 end{bmatrix} $ and $begin{bmatrix} 0&0&0\-i&0&0\0&1&0 end{bmatrix} $ are similar.Is this True/false Clearly both are nilpotent and one is conjucate transpose of other but how to know if they are similar.i'm stuck. Please help me linear-algebra vector-spaces eigenvalues-eigenvectors generalizedeigenvector share | cite | improve this question edited Dec 10 '18 at 6:38 Vasanth Kris asked Dec 10 '18 at 6:19 ...
            Read more