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.






graph-theory







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.






    graph-theory







    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.






      graph-theory







      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




      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

          Moe incest case Sentencing See also References Navigation menu"'Australian Josef Fritzl' fathered four children by daughter""Small town recoils in horror at 'Australian Fritzl' incest case""Victorian rape allegations echo Fritzl case - Just In (Australian Broadcasting Corporation)""Incest father jailed for 22 years""'Australian Fritzl' sentenced to 22 years in prison for abusing daughter for three decades""RSJ v The Queen"

          2009 crimes in AustraliaPeople convicted of incestRape in AustraliaChild abuse incidents and cases Victoria Police Moe, Victoria, Australiarapedphysically abusedviolencediedallegationsNews LimitedinvestigateMelbournedevelopmental problemsintellectually disabledspeech impedimentbirth certificateschargedsexual abuseDNA testspleadedguiltyincestindecent assaultcommon assaultsentencingimprisonmentparolesex offender registryappeal The Moe incest case emerged in February 2007 when a woman, identified as M for legal reasons, reported to Victoria Police in the town of Moe, Victoria, Australia that her 63-year-old father, RSJ, had raped, [1] [2] physically abused, and kept her a virtual prisoner in her own home between 1977 and 2005. Police had known about the alleged abuse since 2005, when M first came forward, but could not act because she did not want to cooperate after her father threatened violence against her mother and siblings. The J family had been known to authorities for more than ...
          Read more

          John Burke, 9th Earl of Clanricarde References Navigation menuA General and heraldic dictionary of the peerage and baronetage of the British EmpireLeigh Rayment's Peerage Pages

          People from County GalwayJacobite military personnel of the Williamite War in IrelandHouse of Burke1642 births1722 deathsMembers of the Irish House of LordsEarls of ClanricardePeers of Ireland created by James II IrishpeerWilliam Burke, 7th Earl of ClanricardeRichardisle of InishbofinWilliamite War in IrelandBattle of AughrimUlick Burke, 1st Viscount GalwayProtestantsprivate act of the English ParliamentCatholicWild GeeseSpainBolognaFontenoyHonora BurkePatrick Sarsfield, 1st Earl of Lucan John Burke, 9th Earl of Clanricarde (1642–1722) was an Irish peer. Burke was a younger son of William Burke, 7th Earl of Clanricarde and succeeded his brother Richard. He was created Baron Bophin (over the isle of Inishbofin where Burke is still a common surname amongst the islanders [1] ) in 1689 and commanded a foot regiment as its colonel during the Williamite War in Ireland. He was taken prisoner at the Battle of Aughrim in 1691 and outlawed. His younger brother Ulick Burke, 1st Viscount G...
          Read more

          Football at the 1986 Brunei Merdeka Games Contents Teams Group stage Knockout stage References Navigation menu"Brunei Merdeka Games 1986".

          Image
          1986 in Asian footballFootball at the Brunei Merdeka Games1986 in Brunei1986 in Singaporean football1986 in Malaysian football1986 in Thai sport Bandar Seri BegawanBruneiMalaysia Cup Football at the 1986 Brunei Merdeka Games Tournament details Host country Brunei Dates 19 July – 27 July Teams 10 Final positions Champions Persib Bandung (1st title) Runners-up Malaysia B Third place   Brunei Fourth place Singapore XI Tournament statistics Matches played 10 Goals scored 25 (2.5 per match) ← 1985 1987 → The football tournament at the 1986 Brunei Merdeka Games was held from July 19 to 27 in Bandar Seri Begawan, Brunei. The tournament was also referred to as the Sultan Hassanal Bolkiah Cup, or the second Brunei Pesta Sukan Cup. Contents 1 Teams 2 Group stage 2.1 Group A 2.2 Group B 3 Knockout stage 3.1 Semi-finals 3.2 Bronze medal match 3.3 Gold medal match 4 References Teams It is likely that the Philippines team was the full national team, bu...
          Read more