Another useful concept in simple graph theory is *contraction* and its result, *minors*
of graphs. The idea is that there are several ways of simplifying a graph in order to study
its properties: cutting edges, removing vertices, and decomposing a graph are all methods we’ve seen before. Contraction is a different technique that works by *merging* vertices, rather than removing them.
Here’s how contraction works. Suppose you have a graph G. Pick a pair of vertices v and w
which are adjacent in G. You can create a graph G’ which is a contraction of G by
replacing v and w with a *single* vertex, and taking any edge in G which is incident on
either v or w, and making it incident on the newly contracted node.
It’s much clearer
in a picture: for example, look at the series of graphs to the right. The first one is
the original graph. Below it, we create a new graph by contracting vertices D and K. D
was adjacent to B, K, and E; K was adjacent to F, G, and D. We *merge* D and K by contracting along the edge connecting them, and the new vertex is adjacent on B, E, F, and G – the union of the adjacencies of D and K.
Then we contract again – this time doing two contractions at once – first contracting
A,B, and and the merged AB with C. The resulting contracted vertices has the union of the adjacencies of A, B, and C, which are the two vertices DK and F.
Finally, we do one more contraction merging H and J.
Contraction allows us to define a relationship, called *minor*, which can be used to define a partial order over graphs: If we have a graph G, and it can be made isomorphic to a graph
H by some series of contractions, then H is called a *minor* of G.
The ordering is based directly on minors: if H is a minor of G, then H≤G.
There are some really interesting theorems that allow us to define
properties of graph structures in terms of minors. For example, there’s
a theorem called Wagner’s theorem, which says that a graph is planar if and
only if it has neither K5 nor K3,3 as minors. Let’s look
at one example:
We start with an eight-node non-planar graph. To show that it’s non-planar, we can
first contract A,B, and then contract E,G – and we end up with K3,3, which
means that K3,3 is a minor of the original, which proves that it’s non-planar.
Another neat theorem involves minors and snarks – and a mistake from a post a couple of days ago. Every snark has Petersen’s graph as a *minor*. (I said *subgraph* the other day.) Of course, it’s not necessarily easy to find the series of contractions. For example,
here’s a nice 20-vertex snark, with the vertices nicely labeled, and a copy of Petersen’s graph next to it. This snark can be contracted to Petersen’s graph in 10 contractions. See if you can figure out which
vertex-pairs to contract.