# 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.

## 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