Prove or disprove that If $G$ is a graph with one or more triangles and contains no subdivision of$ K_5$ as a subgraph, then $G$ is planar.Planar and non-planar graphs, and Kuratowski's TheoremExtending Kuratowski's planarity theorem on finite graphs to countable infinite graphs.Prove that the tesseract graph is non-planarDoes adding more edge to the Triakis Tetrahedral Graph make it non-planar because it contains the a subgaph homeomorphic to $K_3,3$?Prove that if a graph contains a $K_5$ minor, then it's not planarProve that $G$ contains a subdivision of $K_5$ or $K_3,3$ if and only if G contains a $K_5$ or $K_3,3$ minorIf $G$ is a graph of order $n ge 5$ and size $mge 3n - 5$ then $G$ contains a subgraph with minimum degree 4.Disprove: “If a graph $G$ does not have a $K_3,3$ or a $K_5$ as an induced subgraph, then it is planar”Graph Theory - Show that every graph with at most three cycles is planarShow that there exists a $5$-regular planar graph and a $5$-regular nonplanar graph.

Is "conspicuously missing" or "conspicuously" the subject of this sentence?

Why doesn't this Google Translate ad use the word "Translation" instead of "Translate"?

Does a warlock using the Darkness/Devil's Sight combo still have advantage on ranged attacks against a target outside the Darkness?

Could you please stop shuffling the deck and play already?

How strictly should I take "Candidates must be local"?

In the late 1940’s to early 1950’s what technology was available that could melt a LOT of ice?

Counting all the hearts

Vocabulary for giving just numbers, not a full answer

What was the Kree's motivation in Captain Marvel?

Reversed Sudoku

Doesn't allowing a user mode program to access kernel space memory and execute the IN and OUT instructions defeat the purpose of having CPU modes?

Plausibility of Mushroom Buildings

How are showroom/display vehicles prepared?

List elements digit difference sort

Why does the negative sign arise in this thermodynamic relation?

Is it necessary to separate DC power cables and data cables?

Database Backup for data and log files

An alternative proof of an application of Hahn-Banach

How to secure an aircraft at a transient parking space?

How does one describe somebody who is bi-racial?

weren't playing vs didn't play

Hotkey (or other quick way) to insert a keyframe for only one component of a vector-valued property?

Are there historical instances of the capital of a colonising country being temporarily or permanently shifted to one of its colonies?

Good for you! in Russian



Prove or disprove that If $G$ is a graph with one or more triangles and contains no subdivision of$ K_5$ as a subgraph, then $G$ is planar.


Planar and non-planar graphs, and Kuratowski's TheoremExtending Kuratowski's planarity theorem on finite graphs to countable infinite graphs.Prove that the tesseract graph is non-planarDoes adding more edge to the Triakis Tetrahedral Graph make it non-planar because it contains the a subgaph homeomorphic to $K_3,3$?Prove that if a graph contains a $K_5$ minor, then it's not planarProve that $G$ contains a subdivision of $K_5$ or $K_3,3$ if and only if G contains a $K_5$ or $K_3,3$ minorIf $G$ is a graph of order $n ge 5$ and size $mge 3n - 5$ then $G$ contains a subgraph with minimum degree 4.Disprove: “If a graph $G$ does not have a $K_3,3$ or a $K_5$ as an induced subgraph, then it is planar”Graph Theory - Show that every graph with at most three cycles is planarShow that there exists a $5$-regular planar graph and a $5$-regular nonplanar graph.













0












$begingroup$


I'm working in the following graph theory excercise.




Prove or disprove that If $G$ is a graph with one or more triangles and contains no subdivision of$ K_5$ as a subgraph, then $G$ is planar.




I'm thinking about the graph $K_6$ and how is non-planar by Kuratowski's theorem, so the answer would be that the statement is false. But I'm not sure about what does "no subdivision of$ K_5$ as a subgraph" means, any hint or help will be really appreciated.










share|cite|improve this question









$endgroup$
















    0












    $begingroup$


    I'm working in the following graph theory excercise.




    Prove or disprove that If $G$ is a graph with one or more triangles and contains no subdivision of$ K_5$ as a subgraph, then $G$ is planar.




    I'm thinking about the graph $K_6$ and how is non-planar by Kuratowski's theorem, so the answer would be that the statement is false. But I'm not sure about what does "no subdivision of$ K_5$ as a subgraph" means, any hint or help will be really appreciated.










    share|cite|improve this question









    $endgroup$














      0












      0








      0





      $begingroup$


      I'm working in the following graph theory excercise.




      Prove or disprove that If $G$ is a graph with one or more triangles and contains no subdivision of$ K_5$ as a subgraph, then $G$ is planar.




      I'm thinking about the graph $K_6$ and how is non-planar by Kuratowski's theorem, so the answer would be that the statement is false. But I'm not sure about what does "no subdivision of$ K_5$ as a subgraph" means, any hint or help will be really appreciated.










      share|cite|improve this question









      $endgroup$




      I'm working in the following graph theory excercise.




      Prove or disprove that If $G$ is a graph with one or more triangles and contains no subdivision of$ K_5$ as a subgraph, then $G$ is planar.




      I'm thinking about the graph $K_6$ and how is non-planar by Kuratowski's theorem, so the answer would be that the statement is false. But I'm not sure about what does "no subdivision of$ K_5$ as a subgraph" means, any hint or help will be really appreciated.







      graph-theory






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked 2 days ago









      mrazmraz

      44319




      44319




















          1 Answer
          1






          active

          oldest

          votes


















          1












          $begingroup$

          Subdivisions are defined here; essentially you can subdivide a graph by adding extra vertices along edges (as you choose). This adds a bunch of extra vertices with degree $2$.



          When the question says the graph "has no subdivision of $K_5$", it means that no subgraph of the graph is of this form. As a non-example, $K_6$ indeed has a subdivision of $K_5$, as if we remove $3$ edges coming from a single vertex (so that it now has degree $2$), then the resulting graph is a subdivision of $K_5$.



          To give you a hint, if this were true, then we could take any non-planar graph without a subdivision of $K_5$, add in three extra vertices connected in a triangle but disconnected from the rest of the graph, and suddenly it would be planar. That is, every graph with a subdivision of $K_5$ would have to be non-planar. Compare this with Wagner's Theorem (often mistakenly attributed to Kuratowski), to find a non-planar graph without a $K_5$ subdivision, and use it as above to form a counterexample.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            @MishaLavrov Thanks.
            $endgroup$
            – Theo Bendit
            2 days ago










          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%2f3141580%2fprove-or-disprove-that-if-g-is-a-graph-with-one-or-more-triangles-and-contains%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$

          Subdivisions are defined here; essentially you can subdivide a graph by adding extra vertices along edges (as you choose). This adds a bunch of extra vertices with degree $2$.



          When the question says the graph "has no subdivision of $K_5$", it means that no subgraph of the graph is of this form. As a non-example, $K_6$ indeed has a subdivision of $K_5$, as if we remove $3$ edges coming from a single vertex (so that it now has degree $2$), then the resulting graph is a subdivision of $K_5$.



          To give you a hint, if this were true, then we could take any non-planar graph without a subdivision of $K_5$, add in three extra vertices connected in a triangle but disconnected from the rest of the graph, and suddenly it would be planar. That is, every graph with a subdivision of $K_5$ would have to be non-planar. Compare this with Wagner's Theorem (often mistakenly attributed to Kuratowski), to find a non-planar graph without a $K_5$ subdivision, and use it as above to form a counterexample.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            @MishaLavrov Thanks.
            $endgroup$
            – Theo Bendit
            2 days ago















          1












          $begingroup$

          Subdivisions are defined here; essentially you can subdivide a graph by adding extra vertices along edges (as you choose). This adds a bunch of extra vertices with degree $2$.



          When the question says the graph "has no subdivision of $K_5$", it means that no subgraph of the graph is of this form. As a non-example, $K_6$ indeed has a subdivision of $K_5$, as if we remove $3$ edges coming from a single vertex (so that it now has degree $2$), then the resulting graph is a subdivision of $K_5$.



          To give you a hint, if this were true, then we could take any non-planar graph without a subdivision of $K_5$, add in three extra vertices connected in a triangle but disconnected from the rest of the graph, and suddenly it would be planar. That is, every graph with a subdivision of $K_5$ would have to be non-planar. Compare this with Wagner's Theorem (often mistakenly attributed to Kuratowski), to find a non-planar graph without a $K_5$ subdivision, and use it as above to form a counterexample.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            @MishaLavrov Thanks.
            $endgroup$
            – Theo Bendit
            2 days ago













          1












          1








          1





          $begingroup$

          Subdivisions are defined here; essentially you can subdivide a graph by adding extra vertices along edges (as you choose). This adds a bunch of extra vertices with degree $2$.



          When the question says the graph "has no subdivision of $K_5$", it means that no subgraph of the graph is of this form. As a non-example, $K_6$ indeed has a subdivision of $K_5$, as if we remove $3$ edges coming from a single vertex (so that it now has degree $2$), then the resulting graph is a subdivision of $K_5$.



          To give you a hint, if this were true, then we could take any non-planar graph without a subdivision of $K_5$, add in three extra vertices connected in a triangle but disconnected from the rest of the graph, and suddenly it would be planar. That is, every graph with a subdivision of $K_5$ would have to be non-planar. Compare this with Wagner's Theorem (often mistakenly attributed to Kuratowski), to find a non-planar graph without a $K_5$ subdivision, and use it as above to form a counterexample.






          share|cite|improve this answer











          $endgroup$



          Subdivisions are defined here; essentially you can subdivide a graph by adding extra vertices along edges (as you choose). This adds a bunch of extra vertices with degree $2$.



          When the question says the graph "has no subdivision of $K_5$", it means that no subgraph of the graph is of this form. As a non-example, $K_6$ indeed has a subdivision of $K_5$, as if we remove $3$ edges coming from a single vertex (so that it now has degree $2$), then the resulting graph is a subdivision of $K_5$.



          To give you a hint, if this were true, then we could take any non-planar graph without a subdivision of $K_5$, add in three extra vertices connected in a triangle but disconnected from the rest of the graph, and suddenly it would be planar. That is, every graph with a subdivision of $K_5$ would have to be non-planar. Compare this with Wagner's Theorem (often mistakenly attributed to Kuratowski), to find a non-planar graph without a $K_5$ subdivision, and use it as above to form a counterexample.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 2 days ago

























          answered 2 days ago









          Theo BenditTheo Bendit

          19.4k12353




          19.4k12353











          • $begingroup$
            @MishaLavrov Thanks.
            $endgroup$
            – Theo Bendit
            2 days ago
















          • $begingroup$
            @MishaLavrov Thanks.
            $endgroup$
            – Theo Bendit
            2 days ago















          $begingroup$
          @MishaLavrov Thanks.
          $endgroup$
          – Theo Bendit
          2 days ago




          $begingroup$
          @MishaLavrov Thanks.
          $endgroup$
          – Theo Bendit
          2 days ago

















          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%2f3141580%2fprove-or-disprove-that-if-g-is-a-graph-with-one-or-more-triangles-and-contains%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 should I support this large drywall patch? Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How do I cover large gaps in drywall?How do I keep drywall around a patch from crumbling?Can I glue a second layer of drywall?How to patch long strip on drywall?Large drywall patch: how to avoid bulging seams?Drywall Mesh Patch vs. Bulge? To remove or not to remove?How to fix this drywall job?Prep drywall before backsplashWhat's the best way to fix this horrible drywall patch job?Drywall patching using 3M Patch Plus Primer

          random experiment with two different functions on unit interval Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Random variable and probability space notionsRandom Walk with EdgesFinding functions where the increase over a random interval is Poisson distributedNumber of days until dayCan an observed event in fact be of zero probability?Unit random processmodels of coins and uniform distributionHow to get the number of successes given $n$ trials , probability $P$ and a random variable $X$Absorbing Markov chain in a computer. Is “almost every” turned into always convergence in computer executions?Stopped random walk is not uniformly integrable

          Lowndes Grove History Architecture References Navigation menu32°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661132°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661178002500"National Register Information System"Historic houses of South Carolina"Lowndes Grove""+32° 48' 6.00", −79° 57' 58.00""Lowndes Grove, Charleston County (260 St. Margaret St., Charleston)""Lowndes Grove"The Charleston ExpositionIt Happened in South Carolina"Lowndes Grove (House), Saint Margaret Street & Sixth Avenue, Charleston, Charleston County, SC(Photographs)"Plantations of the Carolina Low Countrye