3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Hope this help cpe.kmutt.ac.th/~boon/Graph2/Planar.pdf Or here nptel.ac.in/courses/111104026/lecture38.pdf $\endgroup$ – ً ً Dec 12 '15 at 13:42
  • 1
    $\begingroup$ When they say "$K_{3, 3}$ is not planar. Why? It has a cycle", they presumably mean "Why? Because of a long proof which we won't explain, but in which the most important step is noticing that it has a cycle". I agree it's a confusing statement. It's clearly not literally true that having a cycle makes you non-planar, in fact, all of the examples of planar graphs that are given on that page have several cycles. $\endgroup$ – Jack M Dec 12 '15 at 16:39
  • $\begingroup$ @JackM What is that long proof? Is it related to proving Euler's formula when graph is not a tree and hence contains cycle (as explained from 3:56 of this video)? If yes, I am not completely clear how these two relate. $\endgroup$ – Maha Dec 12 '15 at 17:20
  • $\begingroup$ @Mahesha999 I'm sure there are several proofs of the non-planarity of $K_{3,3}$. I may write one up in a day or so if I have the time. Otherwise you can find the proof I'm thinking of in Douglas West's "Introduction To Graph Theory" in the chapter on planar graphs. $\endgroup$ – Jack M Dec 12 '15 at 17:53
  • $\begingroup$ its not that I have not come across any proof of non planarity of $K_{3,3}$. The one I found in Narsingh Deo's book involves first drawing a square/cycle graph $C_4$, then drawing one of its diagonal. Till this it is planar, However to make it $K_{3,3}$, the other diagonal also needs to be drawn. But then saying that it cannot be drawn without edge crossing. Thus $K_{3,3}$ is non planar... $\endgroup$ – Maha Dec 12 '15 at 18:53
8
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ which proof on that page is concerned with this fact that $K_{3,3}$ is not planar since it has a cycle? $\endgroup$ – Maha Dec 12 '15 at 14:42
  • $\begingroup$ ...can you please point me to the reference which makes it a bit more intuitive? $\endgroup$ – Maha Dec 12 '15 at 15:17
  • $\begingroup$ Is it related to proving Euler's formula when graph is not a tree and hence contains cycle (as explained from 3:56 of this video)? If yes, I am not completely clear how these two relate. $\endgroup$ – Maha Dec 12 '15 at 17:24
  • $\begingroup$ It's a different Euler's formula: $V-E+F=2$. $\endgroup$ – Yuval Filmus Dec 12 '15 at 19:54
  • $\begingroup$ The video talks about the same formula: $n-m+r=2$ as can be seen at 6:35. Its just that she uses $n$ for $V$, $m$ for $E$ and $r$ for $F$. Did you mean that the required formula is different from the one explained in the video. If yes which one is that. If no, its not clicking in my head how this formula indicates that the existence of cycle which appears in any plane drawing makes graph non planar. Can you please tell me sir. $\endgroup$ – Maha Dec 13 '15 at 8:43
4
$\begingroup$

In a comment @MithleshUpadhyay links to a document which is part of the book

Graphs   
An Introductory Approach 
by Robin J. Wilson and John J. Watkins   
John Wiley & Sons, Inc. 1990

It seems that the site you are referencing to does cite this book incompletely. Here is the complete text from the book:

On the other hand, the complete bipartite graph $K_{3,3}$ is not planar, since every drawing of it contains at least one crossing. To see why this is, note that $K_{3,3}$ has a cycle of length $6$ (namely, $uavbwcu$) which must appear in any plane drawing as a hexagon (not necessarily regular). enter image description here
We must now insert the edges $ub$, $vc$, and $wa$. Only one of them can be drawn inside the hexagon, since two or more would cross. Similarly, only one of them can be drawn outside, since two or more would cross.

The paragraph following the picture is missing in the text you read. I think the proof from the original text is completely clear.

Improve this answer
$\endgroup$
3
$\begingroup$

If a,b,c,1,2,3 are the vertices of $K_{3,3}$, then in any planar drawing of $K_{3,3}$ the cycle [1a2b3c1] must appear as a cycle.

For example, if it is drawn in the form of a hexagon, then the edge [1,b] will lie either completely inside the hexagon or completely outside it. Assume that the edge [1,b] lies completely inside the hexagon. The edge [2,c] has to be drawn outside the hexagon or else it will intersect the edge [1,b]. Now [3,a] cannot be drawn without intersecting either edge [1,b] or [2,c].

The same argument is valid if edge [1,b] is drawn outside the hexaon.

Graph of k3,3

Improve this answer
$\endgroup$
4
  • $\begingroup$ I have come across such proof as I have said in the comments to the original question in response to @Jack M. But the original sentence was: because $K_{3,3}$ has a cycle which must appear in any plane drawing. These specific words does not fit in your explanation. I understand the cycle must appear in any plane drawing. And its obvious. If it does not occur, it will be the different graph as circuits are isomorphic invariant.... $\endgroup$ – Maha Dec 13 '15 at 14:12
  • $\begingroup$ ....However, how existence of particular cycle in every planar embedding makes graph non planar? Is it like that this sentence is itself incorrect and it should be: not all cycles can be drawn without edge crossing $\endgroup$ – Maha Dec 13 '15 at 14:17
  • 1
    $\begingroup$ In ANY planar drawing of K3,3 the edges [1a2b3c1] must appear as a cycle. Because of the existence of this particular cycle, the edges [1,b] [2,c] [3,a] cannot be drawn without any intersection, making the graph non planar $\endgroup$ – Smrithi.Prabhu Dec 14 '15 at 12:00
  • $\begingroup$ you make it sound more correct. However the source webpage only says: "$K_{3,3}$ is non planar because it has a cycle which must appear in any plane drawing.". Thats sounds like generalization: "Graph is non planar if it has a cycle which must appear in any plane drawing." It does not add: "certain edges cannot be drawn without any intersection", the way you added: "edges [1,b] [2,c] [3,a] cannot be drawn without any intersection". There can be a planar graph with particular cycle appearing in all plane drawing and no edges crossing. Seems that sentence on source webpage is ill formed. $\endgroup$ – Maha Dec 23 '15 at 11:59
0
$\begingroup$

Maybe this is useful, even if is not the same kind of proof you want.

Every planar graph without cycles of 3 vertices (triangles) should follow this rule (that derives from Euler's rule):

$m \leq 2n - 4$

But $K_{3,3}$ has:

$m = 9$

$n = 6$

$9 \leq 8$

That's absurd, so $K_{3,3}$ is not planar.

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.