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?






graph-theory







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?






    graph-theory







    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?






      graph-theory







      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




      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

          Quarter-circle Tiles

          Image
          up vote 0 down vote favorite I have $99$ identical square tiles, each with a quarter-circle drawn on it like this: [asy] size(1.5cm); draw(Arc((2,0),1,90,180),red+1); draw((0,0)--(2,0)--(2,2)--(0,2)--(0,0)); [/asy] When I arrange the tiles in a $9times 11$ rectangular grid, each with a random orientation, what is the expected value of the number of full circles I form? I think this problem has to do with finding the chance any given 2x2 square has a circle, but I can't find it. expected-value share | cite | improve this question asked Nov 20 at 15:03 6minecraftninja 1 2
          Read more

          build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

          Image
          0 I think it's similiar to NFAs. I replace the finite states of the given automaton for start-states for my new automaton. I do it with $epsilon$ -transition from the start state to the actual finite states of the given automaton. The start state of the given automaton will be my accepting(finite) state of my new one. All transitions will be reversed of course to recognize the reversed word. But how do I have to change the stack of the pushdown automaton? That's tricky. formal-languages automata context-free-grammar share | cite | improve this question edited Nov 29 '18 at 14:20 joee
          Read more

          Mont Emei

          Image
          Mont Emei.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Vue du sommet Wanfo du mont Emei Géographie Altitude 3 099  m , Wanfo Coordonnées 29° 31′ 11″ nord, 103° 19′ 57″ est Administration Pays   Chine Province Sichuan Ville-préfecture Leshan Géolocalisation sur la carte : Sichuan Mont Emei Géolocalisation sur la carte : Chine Mont Emei modifier   Paysage panoramique du mont Emei, incluant le paysage panoramique du grand Bouddha de Leshan *   Patrimoine mondial de l'UNESCO Passerelle en bois sur le versant ouest Pays   Chine Subdivision Sichuan Type Mixte Critères (iv) (vi) (x) Superficie 15 400 ha Numéro d’identification 779 Zone géographique Asie et Pacifique  ** Année d’inscription 1996 (20 e session) * Descriptif officiel UNESCO ** Classification géog
          Read more