Graph minors

A graph H is a minor of a graph G if H is isomorphic to a graph obtained by contracting edges, removing edges and/or removing isolated vertices from G. For example the graph with two vertices and one edge is a minor of any graph with at least one edge.

Problem: Fix a graph H. Find a polynomial time algorithm that decides if a given graph G has H as one of its minors. The algorithm must be polynomial in the number of vertices of G.

Notice that such an algorithm proves that planarity of a graph can be decided in polynomial time.

Graph minors

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.

 

Intersection number of graphs

Points on the unit circle

This problem is from Stanley’s “Enumerative Combinatorics Vol. I”, more precisely problem 12 from Chapter 1 (sadly, no solution is provided there.)

Consider n points arranged in the unit circumference and draw all \binom n2 chords connecting two of the points. Assume that the points are laid out in such a way no three chords intersect in a single point (that is, there are no triple intersections). Into how many regions will the interior of the circle by divided? Stanley says: “Try to give an elegant proof avoiding induction, finite differences, generating functions, summations, and the like.” One can do such a thing.

There’s another problem that involves placing points in the circle. Place 2n points in the circle, and label n of them with a 1, and the remaining n with a -1. Prove we can trace the circle, starting from on of this points, in such a way that the partial sums of the values of the points is always positive, and this can be done both clockwise and anticlockwise. Can you generalize this to a continuous (as opposed to discrete) setting?

 

Points on the unit circle