0
$\begingroup$

Hey I am supposed to determine if this graph is planar. I know, that it is not. But I failed to find $K_{3,3}, K_{5}$ as subgraphs.

enter image description here

Can anyone help?

$\endgroup$
1
  • $\begingroup$ The reason you can't find those subgraphs is because it is planar. $\endgroup$
    – player3236
    Oct 26, 2020 at 12:40

1 Answer 1

2
$\begingroup$

You failed to find those...that should tell you that it is planar, which is true.

To see these, move the two top-most nodes. Move the right one to the SE of the lower right node. Move the left one downward until it's just below the long diagonal from NW to SE.

Short summary: When what you observe and what you "know" are in contradiction, it's time to question what you know.

$\endgroup$
5
  • $\begingroup$ Thanks, but how can you see it? I thought that it is not planar because I cannot draw it without intersecting the edges.. I did not thought about moving the vertices $\endgroup$
    – Peter F.
    Oct 26, 2020 at 12:53
  • $\begingroup$ The graph itself is just a collection called the "vertices" and a list of pairs of vertices. The locations of the dots and arcs in the plane are up to you --- those choices constitute an embedding. How can I "see" where to move the nodes? I've got 50 years of practice. There are algorithms, but for graphs this small, just messing around works well. You might want to visit "planarity.net" for a fun game that lets you practice this a little bit. $\endgroup$ Oct 26, 2020 at 13:09
  • 1
    $\begingroup$ @PeterF. Also see the game Untangle chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html There are also free (with no ads) phone app versions of this puzzle collection. $\endgroup$
    – PM 2Ring
    Oct 26, 2020 at 13:12
  • $\begingroup$ @JohnHughes Thank you so much, I will try it $\endgroup$
    – Peter F.
    Oct 26, 2020 at 13:16
  • $\begingroup$ @PM2Ring Thank you so much $\endgroup$
    – Peter F.
    Oct 26, 2020 at 13:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .