Adding an edge to a maximal planar graph results in topological minors of both $K_5,K_{3,3}$.












2












$begingroup$


I was trying to prove this exercise from Diestel's book:




Show that adding a new edge to a maximal planar graph
of order at least 6 always produces both a $TK_5$ and a $TK_{3,3}$ subgraph.




I used a hint from Diestel's book to get a topological minor of $K_5$, but I had trouble finding the $TK_{3,3}$. I found a solution here (The $K_5$-part is the same thing I did).



However, I don't understand a part of it when they try to find the $TK_{3,3}$ subgraph. They say:




Since $G$ has order at least $6$, there is another vertex $z$ distinct from those
previously mentioned. The construction allows for two cases: either $z$ lies outside the
region bounded by the topological cycle $vu_1wu_2v$ or it lies inside one of the faces of
this region (they are all equivalent).




My question is why cannot $z$ be in the boundary of $vu_1wu_2v$? And it that were possible, the three disjoint paths from $z$ to $u_1,u_2,u_3$ might not be disjoint to the previous drawn paths, which seems to cause trouble when building the $K_{3,3}$-subdivision.






graph-theory proof-explanation planar-graph







share|cite|improve this question











$endgroup$

















    2












    $begingroup$


    I was trying to prove this exercise from Diestel's book:




    Show that adding a new edge to a maximal planar graph
    of order at least 6 always produces both a $TK_5$ and a $TK_{3,3}$ subgraph.




    I used a hint from Diestel's book to get a topological minor of $K_5$, but I had trouble finding the $TK_{3,3}$. I found a solution here (The $K_5$-part is the same thing I did).



    However, I don't understand a part of it when they try to find the $TK_{3,3}$ subgraph. They say:




    Since $G$ has order at least $6$, there is another vertex $z$ distinct from those
    previously mentioned. The construction allows for two cases: either $z$ lies outside the
    region bounded by the topological cycle $vu_1wu_2v$ or it lies inside one of the faces of
    this region (they are all equivalent).




    My question is why cannot $z$ be in the boundary of $vu_1wu_2v$? And it that were possible, the three disjoint paths from $z$ to $u_1,u_2,u_3$ might not be disjoint to the previous drawn paths, which seems to cause trouble when building the $K_{3,3}$-subdivision.






    graph-theory proof-explanation planar-graph







    share|cite|improve this question











    $endgroup$















      2












      2








      2





      $begingroup$


      I was trying to prove this exercise from Diestel's book:




      Show that adding a new edge to a maximal planar graph
      of order at least 6 always produces both a $TK_5$ and a $TK_{3,3}$ subgraph.




      I used a hint from Diestel's book to get a topological minor of $K_5$, but I had trouble finding the $TK_{3,3}$. I found a solution here (The $K_5$-part is the same thing I did).



      However, I don't understand a part of it when they try to find the $TK_{3,3}$ subgraph. They say:




      Since $G$ has order at least $6$, there is another vertex $z$ distinct from those
      previously mentioned. The construction allows for two cases: either $z$ lies outside the
      region bounded by the topological cycle $vu_1wu_2v$ or it lies inside one of the faces of
      this region (they are all equivalent).




      My question is why cannot $z$ be in the boundary of $vu_1wu_2v$? And it that were possible, the three disjoint paths from $z$ to $u_1,u_2,u_3$ might not be disjoint to the previous drawn paths, which seems to cause trouble when building the $K_{3,3}$-subdivision.






      graph-theory proof-explanation planar-graph







      share|cite|improve this question











      $endgroup$




      I was trying to prove this exercise from Diestel's book:




      Show that adding a new edge to a maximal planar graph
      of order at least 6 always produces both a $TK_5$ and a $TK_{3,3}$ subgraph.




      I used a hint from Diestel's book to get a topological minor of $K_5$, but I had trouble finding the $TK_{3,3}$. I found a solution here (The $K_5$-part is the same thing I did).



      However, I don't understand a part of it when they try to find the $TK_{3,3}$ subgraph. They say:




      Since $G$ has order at least $6$, there is another vertex $z$ distinct from those
      previously mentioned. The construction allows for two cases: either $z$ lies outside the
      region bounded by the topological cycle $vu_1wu_2v$ or it lies inside one of the faces of
      this region (they are all equivalent).




      My question is why cannot $z$ be in the boundary of $vu_1wu_2v$? And it that were possible, the three disjoint paths from $z$ to $u_1,u_2,u_3$ might not be disjoint to the previous drawn paths, which seems to cause trouble when building the $K_{3,3}$-subdivision.






      graph-theory proof-explanation planar-graph




      graph-theory proof-explanation planar-graph






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Dec 23 '18 at 8:48









      Alex Ravsky

      41.5k32283




      41.5k32283










      asked Dec 22 '18 at 3:40









      NellNell

      37719




      37719






















          1 Answer
          1






          active

          oldest

          votes


















          2












          $begingroup$

          I think that solution is wrong already at the following point.




          Since $v$ is not adjacent to $w$ (else we could add no edge between them), we can find vertices $u_1$, $u_2$, and $u_3$ lying one on each path that are neighbors of $v$ but not of $w$.




          If a path from $v$ to $w$ has length $2$ then a neighbor $u$ of $v$ at the path is a neighbor of $w$.




          By the edge-maximality of $G$, $u_1$, $u_2$, and $u_3$ induce a cycle.




          This is true, if $v$ has degree three. Otherwise it may fail (for instance, see the picture).



          enter image description here






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            You're right. Fortunately, I had modified that part to just take the three paths in such a way each of them only contained one neighbor of $v$. About the use of the edge maximality of $G$, I think that to produce the subdivision of $K_5$ we only need to make sure all the neighbors of $v$ form a cycle.
            $endgroup$
            – Nell
            Dec 28 '18 at 3:27











          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%2f3049103%2fadding-an-edge-to-a-maximal-planar-graph-results-in-topological-minors-of-both%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$

          I think that solution is wrong already at the following point.




          Since $v$ is not adjacent to $w$ (else we could add no edge between them), we can find vertices $u_1$, $u_2$, and $u_3$ lying one on each path that are neighbors of $v$ but not of $w$.




          If a path from $v$ to $w$ has length $2$ then a neighbor $u$ of $v$ at the path is a neighbor of $w$.




          By the edge-maximality of $G$, $u_1$, $u_2$, and $u_3$ induce a cycle.




          This is true, if $v$ has degree three. Otherwise it may fail (for instance, see the picture).



          enter image description here






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            You're right. Fortunately, I had modified that part to just take the three paths in such a way each of them only contained one neighbor of $v$. About the use of the edge maximality of $G$, I think that to produce the subdivision of $K_5$ we only need to make sure all the neighbors of $v$ form a cycle.
            $endgroup$
            – Nell
            Dec 28 '18 at 3:27
















          2












          $begingroup$

          I think that solution is wrong already at the following point.




          Since $v$ is not adjacent to $w$ (else we could add no edge between them), we can find vertices $u_1$, $u_2$, and $u_3$ lying one on each path that are neighbors of $v$ but not of $w$.




          If a path from $v$ to $w$ has length $2$ then a neighbor $u$ of $v$ at the path is a neighbor of $w$.




          By the edge-maximality of $G$, $u_1$, $u_2$, and $u_3$ induce a cycle.




          This is true, if $v$ has degree three. Otherwise it may fail (for instance, see the picture).



          enter image description here






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            You're right. Fortunately, I had modified that part to just take the three paths in such a way each of them only contained one neighbor of $v$. About the use of the edge maximality of $G$, I think that to produce the subdivision of $K_5$ we only need to make sure all the neighbors of $v$ form a cycle.
            $endgroup$
            – Nell
            Dec 28 '18 at 3:27














          2












          2








          2





          $begingroup$

          I think that solution is wrong already at the following point.




          Since $v$ is not adjacent to $w$ (else we could add no edge between them), we can find vertices $u_1$, $u_2$, and $u_3$ lying one on each path that are neighbors of $v$ but not of $w$.




          If a path from $v$ to $w$ has length $2$ then a neighbor $u$ of $v$ at the path is a neighbor of $w$.




          By the edge-maximality of $G$, $u_1$, $u_2$, and $u_3$ induce a cycle.




          This is true, if $v$ has degree three. Otherwise it may fail (for instance, see the picture).



          enter image description here






          share|cite|improve this answer









          $endgroup$



          I think that solution is wrong already at the following point.




          Since $v$ is not adjacent to $w$ (else we could add no edge between them), we can find vertices $u_1$, $u_2$, and $u_3$ lying one on each path that are neighbors of $v$ but not of $w$.




          If a path from $v$ to $w$ has length $2$ then a neighbor $u$ of $v$ at the path is a neighbor of $w$.




          By the edge-maximality of $G$, $u_1$, $u_2$, and $u_3$ induce a cycle.




          This is true, if $v$ has degree three. Otherwise it may fail (for instance, see the picture).



          enter image description here







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Dec 23 '18 at 8:47









          Alex RavskyAlex Ravsky

          41.5k32283




          41.5k32283












          • $begingroup$
            You're right. Fortunately, I had modified that part to just take the three paths in such a way each of them only contained one neighbor of $v$. About the use of the edge maximality of $G$, I think that to produce the subdivision of $K_5$ we only need to make sure all the neighbors of $v$ form a cycle.
            $endgroup$
            – Nell
            Dec 28 '18 at 3:27


















          • $begingroup$
            You're right. Fortunately, I had modified that part to just take the three paths in such a way each of them only contained one neighbor of $v$. About the use of the edge maximality of $G$, I think that to produce the subdivision of $K_5$ we only need to make sure all the neighbors of $v$ form a cycle.
            $endgroup$
            – Nell
            Dec 28 '18 at 3:27
















          $begingroup$
          You're right. Fortunately, I had modified that part to just take the three paths in such a way each of them only contained one neighbor of $v$. About the use of the edge maximality of $G$, I think that to produce the subdivision of $K_5$ we only need to make sure all the neighbors of $v$ form a cycle.
          $endgroup$
          – Nell
          Dec 28 '18 at 3:27




          $begingroup$
          You're right. Fortunately, I had modified that part to just take the three paths in such a way each of them only contained one neighbor of $v$. About the use of the edge maximality of $G$, I think that to produce the subdivision of $K_5$ we only need to make sure all the neighbors of $v$ form a cycle.
          $endgroup$
          – Nell
          Dec 28 '18 at 3:27


















          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%2f3049103%2fadding-an-edge-to-a-maximal-planar-graph-results-in-topological-minors-of-both%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

          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

          Province de Neuquén

          Image
          Province de Neuquén Provincia del Neuquén .mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Héraldique Drapeau Localisation de la province de Neuquén Administration Pays   Argentine Capitale Neuquén Gouverneur Omar Gutiérrez ISO 3166-2 AR-Q Démographie Gentilé Neuquino/a Population 550 344  hab. (2010) Densité 5,8  hab./km 2 Géographie Superficie 94 078  km 2 Liens Site web http://www.neuquen.gov.ar modifier   La province de Neuquén est une province d'Argentine, qui se trouve à l'extrémité nord-ouest de la Patagonie argentine. Avec une superficie de 94 378  km 2 , elle est la plus petite province des régions australes du pays. Sa géographie s'abîme sur l'imposante Cordillère des Andes. Sommaire 1 Histoire 1.1 Avant la découverte par les Espagnols 1.2 ...
          Read more

          Journaliste

          Image
          Pour les articles homonymes, voir Journaliste (homonymie). Journaliste Journalistes Appellation Journaliste Secteur d'activité Média - Communication Professions voisines Journaliste sportif - Reporter-photographe - Éditorialiste Codes CITP 2451, 2642 IDEO (France) 10197 ROME (France) E1106 modifier - modifier le code - modifier Wikidata Un journaliste est une personne qui recueille, écrit ou distribue des informations. L'activité d'un journaliste est le journalisme. Un journaliste peut travailler sur des sujets généraux ou se spécialiser dans certaines questions. La plupart des journalistes ont tendance à se spécialiser et, en collaborant avec d'autres journalistes, rédigent un article ou mettent en forme un reportage qui couvre l'actualité. Par exemple, un journaliste sportif couvre les nouvelles dans le monde du sport, mais ce journaliste peut aussi faire partie d'un journal qui couvre d'autres su...
          Read more