Intersection number of graphs

Given two graphs G,H, draw them in the plane, in such a way that the drawings intersect in interior point of edges, and in such a way there are finitely many points of intersection. The intersection number of G,H with respect to this drawing is the sum of the number of intersections reduced modulo two. Convince yourself this might depend on the way we draw G,H. Define the self intersection number of G with respect to a good drawing as above to be the sum of self intersections between non-adjacent edges. This might also depend on the drawing. Of course, a planar graph admits 0 as its intersection number, but might also admit 1, as the canonical drawing of K_{2,3} shows.

  1. Show that if G,H are cycles, their intersection number is well defined, and is in fact zero.
  2. Suppose G has the property that for any edge e in G the nonadjacent edges to e form a cycle. Show that the self intersection number is well defined.
  3. Conclude that K_{3,3} and K_5 are not planar by showing they have self intersection number equal to one and satisfy the condition above.

 

Advertisements
Intersection number of graphs

One thought on “Intersection number of graphs

  1. The first problem is mildly easy using the polygonal version of the Jordan curve theorem: pick a vertex v_0 in the first cycle C outside the curve determined by other cycle D. Every intersection vw of an edge of C is paired with the first intersection of the path from w to v_0 in the direction opposite to v. If there is no intersection, stop. If there is one intersection, there is another by the above. Continue. Since there are finitely many intersections, this algorithm stops, and always at an even number of intersections.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s