Self-complementary graph exercise












1












$begingroup$


I'm doing university exercises about planar graphs and they gave me the following:



Let G be a connected, self-complementary planar graph of order n and size
m having four vertices of degree two and the remaining vertices of degree d. If six faces of G are triangles and the remaining faces are pentagons, compute the values of d, n and m.



I'm not sure How Can I figure out the solicited values? I tried reach an equalization using the Euler form, the successions degree form and the sizes form for a complementary graph, but I had not success.



Has someone any idea ?



Thanks a lot!










share|cite|improve this question









$endgroup$

















    1












    $begingroup$


    I'm doing university exercises about planar graphs and they gave me the following:



    Let G be a connected, self-complementary planar graph of order n and size
    m having four vertices of degree two and the remaining vertices of degree d. If six faces of G are triangles and the remaining faces are pentagons, compute the values of d, n and m.



    I'm not sure How Can I figure out the solicited values? I tried reach an equalization using the Euler form, the successions degree form and the sizes form for a complementary graph, but I had not success.



    Has someone any idea ?



    Thanks a lot!










    share|cite|improve this question









    $endgroup$















      1












      1








      1


      1



      $begingroup$


      I'm doing university exercises about planar graphs and they gave me the following:



      Let G be a connected, self-complementary planar graph of order n and size
      m having four vertices of degree two and the remaining vertices of degree d. If six faces of G are triangles and the remaining faces are pentagons, compute the values of d, n and m.



      I'm not sure How Can I figure out the solicited values? I tried reach an equalization using the Euler form, the successions degree form and the sizes form for a complementary graph, but I had not success.



      Has someone any idea ?



      Thanks a lot!










      share|cite|improve this question









      $endgroup$




      I'm doing university exercises about planar graphs and they gave me the following:



      Let G be a connected, self-complementary planar graph of order n and size
      m having four vertices of degree two and the remaining vertices of degree d. If six faces of G are triangles and the remaining faces are pentagons, compute the values of d, n and m.



      I'm not sure How Can I figure out the solicited values? I tried reach an equalization using the Euler form, the successions degree form and the sizes form for a complementary graph, but I had not success.



      Has someone any idea ?



      Thanks a lot!







      graph-theory planar-graph






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Dec 31 '18 at 0:02









      BrunoBernBrunoBern

      153




      153






















          1 Answer
          1






          active

          oldest

          votes


















          2












          $begingroup$

          Since G is self-complementary, it has half the number of edges as a complete graph of the same order.



          $$m = frac{n(n-1)}{4} = 4+(n-4)frac{d}{2}$$



          $$ n^2-n = 16+2nd-8d $$



          Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)



          Check for $d=5$:



          $$ n^2-n = 16+10n-40 $$
          $$ n^2-11n+24=0 implies n={3,8}$$



          In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.



          I will leave it to you to find the graph. Hint: add to the tetrahedron.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
            $endgroup$
            – BrunoBern
            Dec 31 '18 at 3:33










          • $begingroup$
            @BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 3:37










          • $begingroup$
            A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 3:40










          • $begingroup$
            Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
            $endgroup$
            – BrunoBern
            Dec 31 '18 at 15:06












          • $begingroup$
            Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 15: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%2f3057301%2fself-complementary-graph-exercise%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









          2












          $begingroup$

          Since G is self-complementary, it has half the number of edges as a complete graph of the same order.



          $$m = frac{n(n-1)}{4} = 4+(n-4)frac{d}{2}$$



          $$ n^2-n = 16+2nd-8d $$



          Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)



          Check for $d=5$:



          $$ n^2-n = 16+10n-40 $$
          $$ n^2-11n+24=0 implies n={3,8}$$



          In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.



          I will leave it to you to find the graph. Hint: add to the tetrahedron.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
            $endgroup$
            – BrunoBern
            Dec 31 '18 at 3:33










          • $begingroup$
            @BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 3:37










          • $begingroup$
            A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 3:40










          • $begingroup$
            Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
            $endgroup$
            – BrunoBern
            Dec 31 '18 at 15:06












          • $begingroup$
            Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 15:19
















          2












          $begingroup$

          Since G is self-complementary, it has half the number of edges as a complete graph of the same order.



          $$m = frac{n(n-1)}{4} = 4+(n-4)frac{d}{2}$$



          $$ n^2-n = 16+2nd-8d $$



          Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)



          Check for $d=5$:



          $$ n^2-n = 16+10n-40 $$
          $$ n^2-11n+24=0 implies n={3,8}$$



          In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.



          I will leave it to you to find the graph. Hint: add to the tetrahedron.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
            $endgroup$
            – BrunoBern
            Dec 31 '18 at 3:33










          • $begingroup$
            @BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 3:37










          • $begingroup$
            A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 3:40










          • $begingroup$
            Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
            $endgroup$
            – BrunoBern
            Dec 31 '18 at 15:06












          • $begingroup$
            Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 15:19














          2












          2








          2





          $begingroup$

          Since G is self-complementary, it has half the number of edges as a complete graph of the same order.



          $$m = frac{n(n-1)}{4} = 4+(n-4)frac{d}{2}$$



          $$ n^2-n = 16+2nd-8d $$



          Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)



          Check for $d=5$:



          $$ n^2-n = 16+10n-40 $$
          $$ n^2-11n+24=0 implies n={3,8}$$



          In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.



          I will leave it to you to find the graph. Hint: add to the tetrahedron.






          share|cite|improve this answer











          $endgroup$



          Since G is self-complementary, it has half the number of edges as a complete graph of the same order.



          $$m = frac{n(n-1)}{4} = 4+(n-4)frac{d}{2}$$



          $$ n^2-n = 16+2nd-8d $$



          Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)



          Check for $d=5$:



          $$ n^2-n = 16+10n-40 $$
          $$ n^2-11n+24=0 implies n={3,8}$$



          In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.



          I will leave it to you to find the graph. Hint: add to the tetrahedron.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Dec 31 '18 at 2:07

























          answered Dec 31 '18 at 0:44









          Zachary HunterZachary Hunter

          55611




          55611












          • $begingroup$
            Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
            $endgroup$
            – BrunoBern
            Dec 31 '18 at 3:33










          • $begingroup$
            @BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 3:37










          • $begingroup$
            A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 3:40










          • $begingroup$
            Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
            $endgroup$
            – BrunoBern
            Dec 31 '18 at 15:06












          • $begingroup$
            Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 15:19


















          • $begingroup$
            Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
            $endgroup$
            – BrunoBern
            Dec 31 '18 at 3:33










          • $begingroup$
            @BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 3:37










          • $begingroup$
            A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 3:40










          • $begingroup$
            Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
            $endgroup$
            – BrunoBern
            Dec 31 '18 at 15:06












          • $begingroup$
            Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
            $endgroup$
            – Zachary Hunter
            Dec 31 '18 at 15:19
















          $begingroup$
          Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
          $endgroup$
          – BrunoBern
          Dec 31 '18 at 3:33




          $begingroup$
          Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
          $endgroup$
          – BrunoBern
          Dec 31 '18 at 3:33












          $begingroup$
          @BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
          $endgroup$
          – Zachary Hunter
          Dec 31 '18 at 3:37




          $begingroup$
          @BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
          $endgroup$
          – Zachary Hunter
          Dec 31 '18 at 3:37












          $begingroup$
          A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
          $endgroup$
          – Zachary Hunter
          Dec 31 '18 at 3:40




          $begingroup$
          A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
          $endgroup$
          – Zachary Hunter
          Dec 31 '18 at 3:40












          $begingroup$
          Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
          $endgroup$
          – BrunoBern
          Dec 31 '18 at 15:06






          $begingroup$
          Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
          $endgroup$
          – BrunoBern
          Dec 31 '18 at 15:06














          $begingroup$
          Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
          $endgroup$
          – Zachary Hunter
          Dec 31 '18 at 15:19




          $begingroup$
          Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
          $endgroup$
          – Zachary Hunter
          Dec 31 '18 at 15: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%2f3057301%2fself-complementary-graph-exercise%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

          1300-talet

          1300-talet

          Display a custom attribute below product name in the front-end Magento 1.9.3.8