3
$\begingroup$

Hello i have the following graph:

diagram

I'm trying to figure out if it's planar or not. I think it is not planar but i can't find a subgraph that is a subdivision of K3,3 or K5 , to use the kuratowski theorem.

p.s. i can only redraw the graph to show that it is planar or prove that its not planar with kuratowski theorem. NO other methods allowed.

$\endgroup$
  • 1
    $\begingroup$ Put the vertices that are outside the triangle CJD, inside it. $\endgroup$ – user525761 Jan 28 '18 at 19:24
  • $\begingroup$ there is'nt a triangle cjd. the edges are {c,h} , {h,j}, {j,i},{i,d}, {d,c}, I'll update the picture now . $\endgroup$ – Prog Kid Jan 28 '18 at 19:31
3
$\begingroup$

Delete the edges $\{EG\}$ and $\{FH\}$. Then you can do the following:

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you very much for your answer and all the other guys that helped. $\endgroup$ – Prog Kid Jan 28 '18 at 20:45
  • $\begingroup$ Now I understand. I just thought based on some examples that I show on the internet that there must be a direct edge that connects the two vertices. So I couldn't have {JH} and {CH} but only {CJ} that's wrong right? $\endgroup$ – itsundefined Jan 28 '18 at 21:03
  • 1
    $\begingroup$ @itsundefined I wouldn't say wrong. Actually in gifs that show these kind of subgraphs, they superpose (Consider it as $H$ and $J$ are the same) the vertices instead of subdividing the edge as I did. I just made it this way to be more clear again because otherwise it is not easy to see the connections. See commons.wikimedia.org/wiki/File:Kuratowski.gif for Petersen Graph, you will better understand what I'm saying. $\endgroup$ – ArsenBerk Jan 28 '18 at 21:08
2
$\begingroup$

Does the following regrouping help:

enter image description here

Yes it does! If the original graph were planar, you could collapse any two connected vertices into one and still the graph would remain planar. But this way you would get that the above grouped graph, which is $K_{3,3}$, is planar: a contradiction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That would be Wagner's theorem, not Kuratowski's. $\endgroup$ – hmakholm left over Monica Jan 28 '18 at 20:04
  • $\begingroup$ as far as i know for the kuratowski's theorem, (im noob tho) i can delete an edge {u,w} and add a vertice v and the edges {u,v}, {v,w}, not collapsing two vertices. $\endgroup$ – Prog Kid Jan 28 '18 at 20:14
  • $\begingroup$ @Bill Tsek I haven't even heard of those theorems :D. I understand you want to use a particular theorem, but this is just something I cooked up with trial and error. $\endgroup$ – ploosu2 Jan 28 '18 at 20:21
  • $\begingroup$ @ploosu2 I wouldn't rely on this. A planar graph will stay planar for every couple of connected vertices collapsed. However, not every non-planar graph will stay non-planar when applying this method. Try it with a complete graph of 5 nodes. $\endgroup$ – 0lt Sep 4 '18 at 8:05
  • $\begingroup$ @0lt Only the first mentioned is needed here. $\endgroup$ – ploosu2 Sep 4 '18 at 12:44
1
$\begingroup$

Try $K_{3,3}$ with BHI as one of the sides.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.