The Wikipedia definition of the degeneracy of a graph.












0














I'm trying to understand Wikipedia's definition of "Degeneracy (graph theory)" which says:




In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges.




Degeneracy - Wikipedia



But then I look at the example and it does not make sense to me. Here is the graphic:



2-core



Now, from what I understand, a subgraph can be any subset of vertices and edges from the original graph. If so, one vertex can be a subgraph. If so, the 2-degenerate graph has many single vertices (aka subgraphs) that touch more than 2 edges.



I am sure I am missing something, but I don't know what it is.






graph-theory







share|cite|improve this question





























    0














    I'm trying to understand Wikipedia's definition of "Degeneracy (graph theory)" which says:




    In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges.




    Degeneracy - Wikipedia



    But then I look at the example and it does not make sense to me. Here is the graphic:



    2-core



    Now, from what I understand, a subgraph can be any subset of vertices and edges from the original graph. If so, one vertex can be a subgraph. If so, the 2-degenerate graph has many single vertices (aka subgraphs) that touch more than 2 edges.



    I am sure I am missing something, but I don't know what it is.






    graph-theory







    share|cite|improve this question



























      0












      0








      0


      1





      I'm trying to understand Wikipedia's definition of "Degeneracy (graph theory)" which says:




      In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges.




      Degeneracy - Wikipedia



      But then I look at the example and it does not make sense to me. Here is the graphic:



      2-core



      Now, from what I understand, a subgraph can be any subset of vertices and edges from the original graph. If so, one vertex can be a subgraph. If so, the 2-degenerate graph has many single vertices (aka subgraphs) that touch more than 2 edges.



      I am sure I am missing something, but I don't know what it is.






      graph-theory







      share|cite|improve this question















      I'm trying to understand Wikipedia's definition of "Degeneracy (graph theory)" which says:




      In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges.




      Degeneracy - Wikipedia



      But then I look at the example and it does not make sense to me. Here is the graphic:



      2-core



      Now, from what I understand, a subgraph can be any subset of vertices and edges from the original graph. If so, one vertex can be a subgraph. If so, the 2-degenerate graph has many single vertices (aka subgraphs) that touch more than 2 edges.



      I am sure I am missing something, but I don't know what it is.






      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 Nov 21 '18 at 16:14









      Mefitico

      920117




      920117










      asked Nov 21 '18 at 16:09









      spacedustpi

      32




      32






















          1 Answer
          1






          active

          oldest

          votes


















          0














          Each edge of a subgraph must have two vertices. (These vertices need to be in the subgraph.) That is, a single vertex with one or more edges from it, but with the edges not connected to other vertices of the subgraph at their "other ends", is not considered a subgraph.






          share|cite|improve this answer

















          • 1




            Ah yes, in the context of a subgraph, an edge does not exist unless connected on both ends by vertices.
            – spacedustpi
            Nov 21 '18 at 18:13










          • However, if I choose the 4th, 6th, and 10th nodes as the subgraph, the 4th vertices is touching 3 edges whose other ends are connected to vertices. So this is more than a 2-degenerate graph?
            – spacedustpi
            Nov 21 '18 at 18:25










          • If you only choose the 4,6,10 vertices and no edges, that subgraph has each vertex degree 0. If you choose for your subgraph vertices 4,6,10 and edges (4,6), (4,10), (6,10) then each of vertices 4,6,10 has degree 2 in the subgraph.
            – coffeemath
            Nov 21 '18 at 18:33










          • Also wiki definition only says each subgaph has a (i.e. at least one) vertex of degree $d le k$ to be called $k$-degenerate. It doesn't matter if the subgraph has some other vertices of degree more than $k,$ only that at least one vertex in the subgraph has degree $d le k.$
            – coffeemath
            Nov 21 '18 at 18:38










          • I see, I should have included edges too. Anyway I think I get it now. I actually thought it meant no vertex in a subgroup can have more than two edges connected to another vertex.
            – spacedustpi
            Nov 21 '18 at 18:45













          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%2f3007931%2fthe-wikipedia-definition-of-the-degeneracy-of-a-graph%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









          0














          Each edge of a subgraph must have two vertices. (These vertices need to be in the subgraph.) That is, a single vertex with one or more edges from it, but with the edges not connected to other vertices of the subgraph at their "other ends", is not considered a subgraph.






          share|cite|improve this answer

















          • 1




            Ah yes, in the context of a subgraph, an edge does not exist unless connected on both ends by vertices.
            – spacedustpi
            Nov 21 '18 at 18:13










          • However, if I choose the 4th, 6th, and 10th nodes as the subgraph, the 4th vertices is touching 3 edges whose other ends are connected to vertices. So this is more than a 2-degenerate graph?
            – spacedustpi
            Nov 21 '18 at 18:25










          • If you only choose the 4,6,10 vertices and no edges, that subgraph has each vertex degree 0. If you choose for your subgraph vertices 4,6,10 and edges (4,6), (4,10), (6,10) then each of vertices 4,6,10 has degree 2 in the subgraph.
            – coffeemath
            Nov 21 '18 at 18:33










          • Also wiki definition only says each subgaph has a (i.e. at least one) vertex of degree $d le k$ to be called $k$-degenerate. It doesn't matter if the subgraph has some other vertices of degree more than $k,$ only that at least one vertex in the subgraph has degree $d le k.$
            – coffeemath
            Nov 21 '18 at 18:38










          • I see, I should have included edges too. Anyway I think I get it now. I actually thought it meant no vertex in a subgroup can have more than two edges connected to another vertex.
            – spacedustpi
            Nov 21 '18 at 18:45


















          0














          Each edge of a subgraph must have two vertices. (These vertices need to be in the subgraph.) That is, a single vertex with one or more edges from it, but with the edges not connected to other vertices of the subgraph at their "other ends", is not considered a subgraph.






          share|cite|improve this answer

















          • 1




            Ah yes, in the context of a subgraph, an edge does not exist unless connected on both ends by vertices.
            – spacedustpi
            Nov 21 '18 at 18:13










          • However, if I choose the 4th, 6th, and 10th nodes as the subgraph, the 4th vertices is touching 3 edges whose other ends are connected to vertices. So this is more than a 2-degenerate graph?
            – spacedustpi
            Nov 21 '18 at 18:25










          • If you only choose the 4,6,10 vertices and no edges, that subgraph has each vertex degree 0. If you choose for your subgraph vertices 4,6,10 and edges (4,6), (4,10), (6,10) then each of vertices 4,6,10 has degree 2 in the subgraph.
            – coffeemath
            Nov 21 '18 at 18:33










          • Also wiki definition only says each subgaph has a (i.e. at least one) vertex of degree $d le k$ to be called $k$-degenerate. It doesn't matter if the subgraph has some other vertices of degree more than $k,$ only that at least one vertex in the subgraph has degree $d le k.$
            – coffeemath
            Nov 21 '18 at 18:38










          • I see, I should have included edges too. Anyway I think I get it now. I actually thought it meant no vertex in a subgroup can have more than two edges connected to another vertex.
            – spacedustpi
            Nov 21 '18 at 18:45
















          0












          0








          0






          Each edge of a subgraph must have two vertices. (These vertices need to be in the subgraph.) That is, a single vertex with one or more edges from it, but with the edges not connected to other vertices of the subgraph at their "other ends", is not considered a subgraph.






          share|cite|improve this answer












          Each edge of a subgraph must have two vertices. (These vertices need to be in the subgraph.) That is, a single vertex with one or more edges from it, but with the edges not connected to other vertices of the subgraph at their "other ends", is not considered a subgraph.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Nov 21 '18 at 16:21









          coffeemath

          2,4631413




          2,4631413








          • 1




            Ah yes, in the context of a subgraph, an edge does not exist unless connected on both ends by vertices.
            – spacedustpi
            Nov 21 '18 at 18:13










          • However, if I choose the 4th, 6th, and 10th nodes as the subgraph, the 4th vertices is touching 3 edges whose other ends are connected to vertices. So this is more than a 2-degenerate graph?
            – spacedustpi
            Nov 21 '18 at 18:25










          • If you only choose the 4,6,10 vertices and no edges, that subgraph has each vertex degree 0. If you choose for your subgraph vertices 4,6,10 and edges (4,6), (4,10), (6,10) then each of vertices 4,6,10 has degree 2 in the subgraph.
            – coffeemath
            Nov 21 '18 at 18:33










          • Also wiki definition only says each subgaph has a (i.e. at least one) vertex of degree $d le k$ to be called $k$-degenerate. It doesn't matter if the subgraph has some other vertices of degree more than $k,$ only that at least one vertex in the subgraph has degree $d le k.$
            – coffeemath
            Nov 21 '18 at 18:38










          • I see, I should have included edges too. Anyway I think I get it now. I actually thought it meant no vertex in a subgroup can have more than two edges connected to another vertex.
            – spacedustpi
            Nov 21 '18 at 18:45
















          • 1




            Ah yes, in the context of a subgraph, an edge does not exist unless connected on both ends by vertices.
            – spacedustpi
            Nov 21 '18 at 18:13










          • However, if I choose the 4th, 6th, and 10th nodes as the subgraph, the 4th vertices is touching 3 edges whose other ends are connected to vertices. So this is more than a 2-degenerate graph?
            – spacedustpi
            Nov 21 '18 at 18:25










          • If you only choose the 4,6,10 vertices and no edges, that subgraph has each vertex degree 0. If you choose for your subgraph vertices 4,6,10 and edges (4,6), (4,10), (6,10) then each of vertices 4,6,10 has degree 2 in the subgraph.
            – coffeemath
            Nov 21 '18 at 18:33










          • Also wiki definition only says each subgaph has a (i.e. at least one) vertex of degree $d le k$ to be called $k$-degenerate. It doesn't matter if the subgraph has some other vertices of degree more than $k,$ only that at least one vertex in the subgraph has degree $d le k.$
            – coffeemath
            Nov 21 '18 at 18:38










          • I see, I should have included edges too. Anyway I think I get it now. I actually thought it meant no vertex in a subgroup can have more than two edges connected to another vertex.
            – spacedustpi
            Nov 21 '18 at 18:45










          1




          1




          Ah yes, in the context of a subgraph, an edge does not exist unless connected on both ends by vertices.
          – spacedustpi
          Nov 21 '18 at 18:13




          Ah yes, in the context of a subgraph, an edge does not exist unless connected on both ends by vertices.
          – spacedustpi
          Nov 21 '18 at 18:13












          However, if I choose the 4th, 6th, and 10th nodes as the subgraph, the 4th vertices is touching 3 edges whose other ends are connected to vertices. So this is more than a 2-degenerate graph?
          – spacedustpi
          Nov 21 '18 at 18:25




          However, if I choose the 4th, 6th, and 10th nodes as the subgraph, the 4th vertices is touching 3 edges whose other ends are connected to vertices. So this is more than a 2-degenerate graph?
          – spacedustpi
          Nov 21 '18 at 18:25












          If you only choose the 4,6,10 vertices and no edges, that subgraph has each vertex degree 0. If you choose for your subgraph vertices 4,6,10 and edges (4,6), (4,10), (6,10) then each of vertices 4,6,10 has degree 2 in the subgraph.
          – coffeemath
          Nov 21 '18 at 18:33




          If you only choose the 4,6,10 vertices and no edges, that subgraph has each vertex degree 0. If you choose for your subgraph vertices 4,6,10 and edges (4,6), (4,10), (6,10) then each of vertices 4,6,10 has degree 2 in the subgraph.
          – coffeemath
          Nov 21 '18 at 18:33












          Also wiki definition only says each subgaph has a (i.e. at least one) vertex of degree $d le k$ to be called $k$-degenerate. It doesn't matter if the subgraph has some other vertices of degree more than $k,$ only that at least one vertex in the subgraph has degree $d le k.$
          – coffeemath
          Nov 21 '18 at 18:38




          Also wiki definition only says each subgaph has a (i.e. at least one) vertex of degree $d le k$ to be called $k$-degenerate. It doesn't matter if the subgraph has some other vertices of degree more than $k,$ only that at least one vertex in the subgraph has degree $d le k.$
          – coffeemath
          Nov 21 '18 at 18:38












          I see, I should have included edges too. Anyway I think I get it now. I actually thought it meant no vertex in a subgroup can have more than two edges connected to another vertex.
          – spacedustpi
          Nov 21 '18 at 18:45






          I see, I should have included edges too. Anyway I think I get it now. I actually thought it meant no vertex in a subgroup can have more than two edges connected to another vertex.
          – spacedustpi
          Nov 21 '18 at 18:45




















          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.





          Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


          Please pay close attention to the following guidance:


          • 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.


          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%2f3007931%2fthe-wikipedia-definition-of-the-degeneracy-of-a-graph%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

          How to send String Array data to Server using php in android

          Image
          0 I have a String array which contains value string array = {6,37,38,837,7,...} and I have also used some string values. I want to send that all string values and string array to my database which is located at server side. When I am click on submit button the data will stored in table. On the PHP side I want to read this array as it is,other thing i will do at background means PHP side. See my below code then you will get it what I am says. Here is my code: public class Hotels extends Activity { // Declare Variables JSONArray jsonarray = null; private static final String TAG_ID = "id"; public static final String TAG_NAME = "name"; public static final String TAG_LOCATION = "location"; public static final String TAG_DESC = "description"; String f_date, l_date;...
          Read more

          Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

          Image
          up vote 5 down vote favorite 2 I would like to make it so that the vertical space below the title of each chapter is the same when using the Bjornstrup package (i.e. so that the descenders do not affect the spacing - as shown by the red arrow in the picture below). I think I'm fairly happy with the spacing around "A chapter", so I'd really like titles without descenders (e.g. "Contents") to have the same vertical spacing as "A chapter" below the title. I would also like to remove the large "0" in the contents title. Any help appreciated, as always. documentclass[11pt,a4paper]{book} % Packages[![enter image description here][1]][1] usepackage[left=3.5cm, right=3.5cm, top=4.3cm, bottom=4.25cm]{geometry} usepackage[utf8]{inputenc} usepackage{libertine} usepackage[libertine]{newtx...
          Read more

          Is anime1.com a legal site for watching anime?

          Image
          up vote 4 down vote favorite 1 Other anime streaming sites are blocking my IP because I'm Iranian while anime1.com isn't. I wanted to know if it's legal to watch/stream anime from this site. Thanks. anime-production share | improve this question edited Nov 27 at 22:38 W. Are 1,599 2 23 asked Nov 27 at 20:36 mhnajafi 23 3 add a comment ...
          Read more