Given two graphs , 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 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 . Define the *self intersection number *of 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 as its intersection number, but might also admit , as the canonical drawing of shows.

- Show that if are cycles, their intersection number is well defined, and is in fact zero.
- Suppose has the property that for any edge in the nonadjacent edges to form a cycle. Show that the self intersection number is well defined.
- Conclude that and are not planar by showing they have self intersection number equal to one and satisfy the condition above.

Advertisements

The first problem is mildly easy using the polygonal version of the Jordan curve theorem: pick a vertex in the first cycle outside the curve determined by other cycle . Every intersection of an edge of is paired with the first intersection of the path from to in the direction opposite to . 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.

LikeLike