« Some norm stuff
Another chapter in the advisor search »

Planarity of a bipartite graph

I printed out the first assignment for my combinatorics course today, and after looking at it, decided that I should start studying immediately. Those problems look scary: I can only imagine how much more involved they get after the first week.

Here’s another problem I came across while reading the textbook (A Course in Combinatorics):

The complete bipartite graph K_{n,m} has n+m vertices a_1, \dots, a_n and b_1, \ldots, b_m, and as edges all mn pairs \{a_i, b_j\}. Show that K_{3,3} is not planar.

At this point, all that has been mentioned about planarity of a graph is the basic definition: a graph is planar if it can be drawn on the plane in such a manner that no two edges cross, so I’m confused as to whether I’m supposed to actually be able to figure this out in a reasonable amount of time given what I already know. Or is this a motivational question?

This entry was posted on Monday, October 1st, 2007 at 7:08 pm and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

6 Responses to “Planarity of a bipartite graph”

  1. Robert Says:
    October 2nd, 2007 at 1:06 pm

    If you haven’t been given any theorems about planar graphs, I wonder if you are just expected to reason through it by describing the reason you can’t draw such a graph. For example, if you connect a1 to each of b1 and b2, and then connect a2 to each of b1 and b2, you have a closed curve (circuit?). Add in a1-b3 and a2-b3 and you have another circuit… well, another pair of circuits. One of the points bi will have to fall inside of one of the circuits, and it will be inaccessible from a3.

    Did I say too much? Is this too elementary/non-rigorous?

  2. Robert Says:
    October 2nd, 2007 at 1:10 pm

    Oops–it’s only inaccessible from a3 if a3 isn’t in the circuit with it… if it IS in the circuit, then one of the other two bi’s is unreachable.

  3. Alex Says:
    October 5th, 2007 at 1:51 pm

    That seems to be the gist of it– convinces me pictorially — but it isn’t rigorous enough for me :)
    Nice to hear from you though, Robert.

  4. Maya Incaand Says:
    October 7th, 2007 at 7:37 am

    That’s about as rigorous as you are going to get! (or need).

    A planar graph cannot have K3,3 or K5 as a minor (ie reached by continuous edge deletion or contraction). (Kuratowski)

    http://mathworld.wolfram.com/GraphMinor.html

    Then if you want to get heavy, Robertson-Seymour.

  5. D. Eppstein Says:
    October 7th, 2007 at 10:18 am

    They may be expecting you to find the proof that follows from Euler’s formula V-E+F=2 and from the observation that in a bipartite planar graph each face has at least four edges.

  6. Kennedy Says:
    October 30th, 2007 at 3:09 pm

    This is a old and well known puzzle.
    http://mathforum.org/dr.math/faq/faq.3utilities.html

Leave a Reply