Is there a graph of 40 vertices of grade 1 to 40?












1












$begingroup$


I’m trying to check if a graph with $40$ vertices with $deg(v_1) = 1$, $deg(v_2)= 2$, $cdots$ , $deg(v_{40}) = 40$ exists.
No other characteristics are known about this graph.



I suppose that a graph like that can’t exist simply because the vertex $40$ cannot have degree $40$. Is my assumption correct or is strictly referred to the hypothesis of a connected graph and it’s not enough?










share|cite|improve this question











$endgroup$

















    1












    $begingroup$


    I’m trying to check if a graph with $40$ vertices with $deg(v_1) = 1$, $deg(v_2)= 2$, $cdots$ , $deg(v_{40}) = 40$ exists.
    No other characteristics are known about this graph.



    I suppose that a graph like that can’t exist simply because the vertex $40$ cannot have degree $40$. Is my assumption correct or is strictly referred to the hypothesis of a connected graph and it’s not enough?










    share|cite|improve this question











    $endgroup$















      1












      1








      1





      $begingroup$


      I’m trying to check if a graph with $40$ vertices with $deg(v_1) = 1$, $deg(v_2)= 2$, $cdots$ , $deg(v_{40}) = 40$ exists.
      No other characteristics are known about this graph.



      I suppose that a graph like that can’t exist simply because the vertex $40$ cannot have degree $40$. Is my assumption correct or is strictly referred to the hypothesis of a connected graph and it’s not enough?










      share|cite|improve this question











      $endgroup$




      I’m trying to check if a graph with $40$ vertices with $deg(v_1) = 1$, $deg(v_2)= 2$, $cdots$ , $deg(v_{40}) = 40$ exists.
      No other characteristics are known about this graph.



      I suppose that a graph like that can’t exist simply because the vertex $40$ cannot have degree $40$. Is my assumption correct or is strictly referred to the hypothesis of a connected graph and it’s not enough?







      graph-theory






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Dec 20 '18 at 10:24









      Ankit Kumar

      1,494221




      1,494221










      asked Dec 20 '18 at 10:16









      PCNFPCNF

      1338




      1338






















          1 Answer
          1






          active

          oldest

          votes


















          1












          $begingroup$

          It depends on the kind of a graph. If it's a simple graph, your argument is absolutely correct. But, if it's not a simple graph, and there can be multiple edges between 2 vertices or loops, then we can have this graph. One of the many possible graphs in that case can be:-



          (Note that i'll take $deg(v_i)=i$)



          $v_1$ will be connected to $v_2$ with one edge. $v_{2i}$, where $i$ is integer, is connected to $v_{2i-1}$ and $v_{2i+1}$ with i edges each. $v_{2i+1}$, where $i$ is integer, is connected to $v_{2i}$ via $i$ edges and with $v_{2i+2}$ via i+1 edges. Finally, $v_{40}$ will be connected to $v_{39}$ via $20$ edges. It can then have $10$ self loops, with each loop contributing $2$ to its degree, giving $deg(v_{40})=40$





          EDIT:



          Since it was asked to do it do it without self-loops, we can do it in this way:-



          Connect (1) $$v_{40}->v_{1}, v_2,cdots ,v_{39} $$
          $$v_{39}->v_{2}, v_3,cdots ,v_{38} $$
          $$v_{38}->v_{3}, v_4,cdots ,v_{37} $$
          $$cdots $$
          $$v_{22}->v_{19}, v_{20}, ,v_{21} $$
          $$v_{21}->v_{20}$$



          Then (2) Join $v_{20+2i}$ to $v_{20+2i-1}$.



          In this way, for $v_i$, $ileq 20$, it'll come only i times in the above mentioned "joining". For $v_{20+i}$, $1leq ileq 20$, it'll be connected to vertices $v_{20-i+1}$ to $v_{20+i-1}$ via pairing (1) $implies$ contributes $2(i-1)+1$ to degree. Also, it also connected to all the vertices above it, again via (1) pairing $implies$ contributes $40-20-i$ to degree. And finally, another vertex via (2) pairing $implies$ contributes $1$ to degree. Final degree $=(2i-2+1)+(40-20-i)+1=20+i$.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Thanks for your answer. I'm reviewing the notes where this question is being asked. In general, in the discussion it is assumed that all the graphs are finite graphs with no self loops. Multiple edges between two vertices are allowed. I think we can also use this information too.
            $endgroup$
            – PCNF
            Dec 20 '18 at 10:50












          • $begingroup$
            @PCNF I've edited. Take a look. Further, it might confuse you a bit, because I know I wasn't able to write it as neatly as I wanted to, so feel free to ask!
            $endgroup$
            – Ankit Kumar
            Dec 20 '18 at 11:35











          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%2f3047368%2fis-there-a-graph-of-40-vertices-of-grade-1-to-40%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









          1












          $begingroup$

          It depends on the kind of a graph. If it's a simple graph, your argument is absolutely correct. But, if it's not a simple graph, and there can be multiple edges between 2 vertices or loops, then we can have this graph. One of the many possible graphs in that case can be:-



          (Note that i'll take $deg(v_i)=i$)



          $v_1$ will be connected to $v_2$ with one edge. $v_{2i}$, where $i$ is integer, is connected to $v_{2i-1}$ and $v_{2i+1}$ with i edges each. $v_{2i+1}$, where $i$ is integer, is connected to $v_{2i}$ via $i$ edges and with $v_{2i+2}$ via i+1 edges. Finally, $v_{40}$ will be connected to $v_{39}$ via $20$ edges. It can then have $10$ self loops, with each loop contributing $2$ to its degree, giving $deg(v_{40})=40$





          EDIT:



          Since it was asked to do it do it without self-loops, we can do it in this way:-



          Connect (1) $$v_{40}->v_{1}, v_2,cdots ,v_{39} $$
          $$v_{39}->v_{2}, v_3,cdots ,v_{38} $$
          $$v_{38}->v_{3}, v_4,cdots ,v_{37} $$
          $$cdots $$
          $$v_{22}->v_{19}, v_{20}, ,v_{21} $$
          $$v_{21}->v_{20}$$



          Then (2) Join $v_{20+2i}$ to $v_{20+2i-1}$.



          In this way, for $v_i$, $ileq 20$, it'll come only i times in the above mentioned "joining". For $v_{20+i}$, $1leq ileq 20$, it'll be connected to vertices $v_{20-i+1}$ to $v_{20+i-1}$ via pairing (1) $implies$ contributes $2(i-1)+1$ to degree. Also, it also connected to all the vertices above it, again via (1) pairing $implies$ contributes $40-20-i$ to degree. And finally, another vertex via (2) pairing $implies$ contributes $1$ to degree. Final degree $=(2i-2+1)+(40-20-i)+1=20+i$.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Thanks for your answer. I'm reviewing the notes where this question is being asked. In general, in the discussion it is assumed that all the graphs are finite graphs with no self loops. Multiple edges between two vertices are allowed. I think we can also use this information too.
            $endgroup$
            – PCNF
            Dec 20 '18 at 10:50












          • $begingroup$
            @PCNF I've edited. Take a look. Further, it might confuse you a bit, because I know I wasn't able to write it as neatly as I wanted to, so feel free to ask!
            $endgroup$
            – Ankit Kumar
            Dec 20 '18 at 11:35
















          1












          $begingroup$

          It depends on the kind of a graph. If it's a simple graph, your argument is absolutely correct. But, if it's not a simple graph, and there can be multiple edges between 2 vertices or loops, then we can have this graph. One of the many possible graphs in that case can be:-



          (Note that i'll take $deg(v_i)=i$)



          $v_1$ will be connected to $v_2$ with one edge. $v_{2i}$, where $i$ is integer, is connected to $v_{2i-1}$ and $v_{2i+1}$ with i edges each. $v_{2i+1}$, where $i$ is integer, is connected to $v_{2i}$ via $i$ edges and with $v_{2i+2}$ via i+1 edges. Finally, $v_{40}$ will be connected to $v_{39}$ via $20$ edges. It can then have $10$ self loops, with each loop contributing $2$ to its degree, giving $deg(v_{40})=40$





          EDIT:



          Since it was asked to do it do it without self-loops, we can do it in this way:-



          Connect (1) $$v_{40}->v_{1}, v_2,cdots ,v_{39} $$
          $$v_{39}->v_{2}, v_3,cdots ,v_{38} $$
          $$v_{38}->v_{3}, v_4,cdots ,v_{37} $$
          $$cdots $$
          $$v_{22}->v_{19}, v_{20}, ,v_{21} $$
          $$v_{21}->v_{20}$$



          Then (2) Join $v_{20+2i}$ to $v_{20+2i-1}$.



          In this way, for $v_i$, $ileq 20$, it'll come only i times in the above mentioned "joining". For $v_{20+i}$, $1leq ileq 20$, it'll be connected to vertices $v_{20-i+1}$ to $v_{20+i-1}$ via pairing (1) $implies$ contributes $2(i-1)+1$ to degree. Also, it also connected to all the vertices above it, again via (1) pairing $implies$ contributes $40-20-i$ to degree. And finally, another vertex via (2) pairing $implies$ contributes $1$ to degree. Final degree $=(2i-2+1)+(40-20-i)+1=20+i$.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Thanks for your answer. I'm reviewing the notes where this question is being asked. In general, in the discussion it is assumed that all the graphs are finite graphs with no self loops. Multiple edges between two vertices are allowed. I think we can also use this information too.
            $endgroup$
            – PCNF
            Dec 20 '18 at 10:50












          • $begingroup$
            @PCNF I've edited. Take a look. Further, it might confuse you a bit, because I know I wasn't able to write it as neatly as I wanted to, so feel free to ask!
            $endgroup$
            – Ankit Kumar
            Dec 20 '18 at 11:35














          1












          1








          1





          $begingroup$

          It depends on the kind of a graph. If it's a simple graph, your argument is absolutely correct. But, if it's not a simple graph, and there can be multiple edges between 2 vertices or loops, then we can have this graph. One of the many possible graphs in that case can be:-



          (Note that i'll take $deg(v_i)=i$)



          $v_1$ will be connected to $v_2$ with one edge. $v_{2i}$, where $i$ is integer, is connected to $v_{2i-1}$ and $v_{2i+1}$ with i edges each. $v_{2i+1}$, where $i$ is integer, is connected to $v_{2i}$ via $i$ edges and with $v_{2i+2}$ via i+1 edges. Finally, $v_{40}$ will be connected to $v_{39}$ via $20$ edges. It can then have $10$ self loops, with each loop contributing $2$ to its degree, giving $deg(v_{40})=40$





          EDIT:



          Since it was asked to do it do it without self-loops, we can do it in this way:-



          Connect (1) $$v_{40}->v_{1}, v_2,cdots ,v_{39} $$
          $$v_{39}->v_{2}, v_3,cdots ,v_{38} $$
          $$v_{38}->v_{3}, v_4,cdots ,v_{37} $$
          $$cdots $$
          $$v_{22}->v_{19}, v_{20}, ,v_{21} $$
          $$v_{21}->v_{20}$$



          Then (2) Join $v_{20+2i}$ to $v_{20+2i-1}$.



          In this way, for $v_i$, $ileq 20$, it'll come only i times in the above mentioned "joining". For $v_{20+i}$, $1leq ileq 20$, it'll be connected to vertices $v_{20-i+1}$ to $v_{20+i-1}$ via pairing (1) $implies$ contributes $2(i-1)+1$ to degree. Also, it also connected to all the vertices above it, again via (1) pairing $implies$ contributes $40-20-i$ to degree. And finally, another vertex via (2) pairing $implies$ contributes $1$ to degree. Final degree $=(2i-2+1)+(40-20-i)+1=20+i$.






          share|cite|improve this answer











          $endgroup$



          It depends on the kind of a graph. If it's a simple graph, your argument is absolutely correct. But, if it's not a simple graph, and there can be multiple edges between 2 vertices or loops, then we can have this graph. One of the many possible graphs in that case can be:-



          (Note that i'll take $deg(v_i)=i$)



          $v_1$ will be connected to $v_2$ with one edge. $v_{2i}$, where $i$ is integer, is connected to $v_{2i-1}$ and $v_{2i+1}$ with i edges each. $v_{2i+1}$, where $i$ is integer, is connected to $v_{2i}$ via $i$ edges and with $v_{2i+2}$ via i+1 edges. Finally, $v_{40}$ will be connected to $v_{39}$ via $20$ edges. It can then have $10$ self loops, with each loop contributing $2$ to its degree, giving $deg(v_{40})=40$





          EDIT:



          Since it was asked to do it do it without self-loops, we can do it in this way:-



          Connect (1) $$v_{40}->v_{1}, v_2,cdots ,v_{39} $$
          $$v_{39}->v_{2}, v_3,cdots ,v_{38} $$
          $$v_{38}->v_{3}, v_4,cdots ,v_{37} $$
          $$cdots $$
          $$v_{22}->v_{19}, v_{20}, ,v_{21} $$
          $$v_{21}->v_{20}$$



          Then (2) Join $v_{20+2i}$ to $v_{20+2i-1}$.



          In this way, for $v_i$, $ileq 20$, it'll come only i times in the above mentioned "joining". For $v_{20+i}$, $1leq ileq 20$, it'll be connected to vertices $v_{20-i+1}$ to $v_{20+i-1}$ via pairing (1) $implies$ contributes $2(i-1)+1$ to degree. Also, it also connected to all the vertices above it, again via (1) pairing $implies$ contributes $40-20-i$ to degree. And finally, another vertex via (2) pairing $implies$ contributes $1$ to degree. Final degree $=(2i-2+1)+(40-20-i)+1=20+i$.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Dec 20 '18 at 11:34

























          answered Dec 20 '18 at 10:33









          Ankit KumarAnkit Kumar

          1,494221




          1,494221












          • $begingroup$
            Thanks for your answer. I'm reviewing the notes where this question is being asked. In general, in the discussion it is assumed that all the graphs are finite graphs with no self loops. Multiple edges between two vertices are allowed. I think we can also use this information too.
            $endgroup$
            – PCNF
            Dec 20 '18 at 10:50












          • $begingroup$
            @PCNF I've edited. Take a look. Further, it might confuse you a bit, because I know I wasn't able to write it as neatly as I wanted to, so feel free to ask!
            $endgroup$
            – Ankit Kumar
            Dec 20 '18 at 11:35


















          • $begingroup$
            Thanks for your answer. I'm reviewing the notes where this question is being asked. In general, in the discussion it is assumed that all the graphs are finite graphs with no self loops. Multiple edges between two vertices are allowed. I think we can also use this information too.
            $endgroup$
            – PCNF
            Dec 20 '18 at 10:50












          • $begingroup$
            @PCNF I've edited. Take a look. Further, it might confuse you a bit, because I know I wasn't able to write it as neatly as I wanted to, so feel free to ask!
            $endgroup$
            – Ankit Kumar
            Dec 20 '18 at 11:35
















          $begingroup$
          Thanks for your answer. I'm reviewing the notes where this question is being asked. In general, in the discussion it is assumed that all the graphs are finite graphs with no self loops. Multiple edges between two vertices are allowed. I think we can also use this information too.
          $endgroup$
          – PCNF
          Dec 20 '18 at 10:50






          $begingroup$
          Thanks for your answer. I'm reviewing the notes where this question is being asked. In general, in the discussion it is assumed that all the graphs are finite graphs with no self loops. Multiple edges between two vertices are allowed. I think we can also use this information too.
          $endgroup$
          – PCNF
          Dec 20 '18 at 10:50














          $begingroup$
          @PCNF I've edited. Take a look. Further, it might confuse you a bit, because I know I wasn't able to write it as neatly as I wanted to, so feel free to ask!
          $endgroup$
          – Ankit Kumar
          Dec 20 '18 at 11:35




          $begingroup$
          @PCNF I've edited. Take a look. Further, it might confuse you a bit, because I know I wasn't able to write it as neatly as I wanted to, so feel free to ask!
          $endgroup$
          – Ankit Kumar
          Dec 20 '18 at 11:35


















          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%2f3047368%2fis-there-a-graph-of-40-vertices-of-grade-1-to-40%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

          Ellipse (mathématiques)

          Quarter-circle Tiles

          Mont Emei