patternMinor
Non planarity of K3,3
Viewed 0 times
planaritynonstackoverflow
Problem
I am reading about planar graphs from this site.
It says:
The complete bipartite graph K3,3 is not planar, since every drawing of K3,3contains at least one crossing. why? because K3,3 has a cycle which must appear in any plane drawing.
I am not able to get what cycle which must appear in any plane drawing has to do with edge crossing. Can't a cycle appear in plane drawing without crossing edges and thus letting the graph be planar? I must be missing something stupid.
It says:
The complete bipartite graph K3,3 is not planar, since every drawing of K3,3contains at least one crossing. why? because K3,3 has a cycle which must appear in any plane drawing.
I am not able to get what cycle which must appear in any plane drawing has to do with edge crossing. Can't a cycle appear in plane drawing without crossing edges and thus letting the graph be planar? I must be missing something stupid.
Solution
This explanation is wrong. In principle you could prove that $K_{3,3}$ is not planar by enumerating all types of planar embeddings, and show that some paths must cross. If I remember correctly this is the path chosen in some lecture notes, so if you look around you might be able to find this argument. Another route, taken by your lecture notes, is to use Euler's formula.
When your notes say that $K_{3,3}$ isn't planar since it "has a cycle", they were trying to provide you some intuition, not too successfully I reckon. The claim requires a proof which is indeed given later in the notes.
When your notes say that $K_{3,3}$ isn't planar since it "has a cycle", they were trying to provide you some intuition, not too successfully I reckon. The claim requires a proof which is indeed given later in the notes.
Context
StackExchange Computer Science Q#50645, answer score: 8
Revisions (0)
No revisions yet.