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.
One thing that we often want to do is break a graph into pieces in a way that preserves
the structural relations between the vertices in any part. Doing that is called
*decomposing* the graph. Decomposition is a useful technique because many ways
of studying the structure of a graph, and many algorithms over graphs can work by
decomposing the graph, studying the elements of the decomposition, and then combining
the results.
To be formal: a graph G can be decomposed into a set of subgraphs {G1, G2, G3, …}, where the edges of each of the Gis are
*disjoint* subsets of the edges of G. So in a decomposition of G, *vertices* can be shared between elements of the decomposition, but *edges* cannot.
In addition to doing vertex and face colorings of a graph, you can also do edge colorings. In an edge coloring, no two edges which are incident on the same vertex can share the same color. In general, edge coloring doesn’t get as much attention as vertex coloring or face coloring, but it can be an interesting subject. Today I’m going to show you an example of a really clever visual proof technique called *graph turning* to prove a statement about the edge colorings of complete graphs.
Just like a graph has a chromatic index for its vertex coloring, it’s got a chromatic
index for its edge coloring. The edge chromatic index of a graph G is the minimum number of colors in any edge-coloring of G. The theorem that I’m going to prove for you is about the edge chromatic index of complete graphs with 2n vertices for some integer n:
**The edge-chromatic index of a complete graph K2n = 2n-1.**
Naming Some Special Graphs
When we talk about graph theory – particularly when we get to some of the
interesting theorems – we end up referencing certain common graphs or type of graphs
by name. In my last post, I had to work in the definition of snark, and struggle around
to avoid mentioning another one, so it seems like as good a time as any to run through
some of the basics. This won’t be an exciting post, but you’ve got to do the definitions sometime. And there’s a bunch of pretty pictures, and even an interesting simple proof or two.
Coloring general graphs is, as I said in my last post, quite difficult. But if you can restrict the structure of the graph, you can change the problem in a way that makes it *much* easier. The classic example of this is *planar graphs*.
A planar graph is a graph which can be drawn on a plane with no edges crossing. Every planar graph is also the structural equivalent to a map, where the vertices corresponding to two countries on a map are adjacent if and only if the countries share a border in the map. (A border here has non-zero length, so two countries that only meet in a corner don’t share a border.) You can see an example of a map with its corresponding planar graph overlayed to the right.
Graph coloring is deceptively simple. The idea of coloring a graph is very straightforward, and it seems as if it should be relatively straightforward to find a coloring. It turns out to not be – in fact, it’s extremely difficult. A simple algorithm for graph coloring is easy to describe, but potentially extremely expensive to run.
One kind of graph problem that’s extremely widely used in computer science is called graph coloring. There’s two versions of it, *vertex coloring*, and *face coloring*.
Vertex coloring is the one that’s more widely used. Edge coloring problems are all variations on the following: given a graph *G=(V,E)*, find a mapping of colors to vertices, such than if two vertices are adjacent, they’re assigned different colors?
The variants of the vertex coloring problem are things like:
* What’s the *minimum* number of colors (aka the *chromatic number* of the graph)
that can be used to color a graph?
* Given an integer N, can you find an N-coloring of the graph?
The face coloring problem is more complicated to describe. Suppose you have a *planar* graph. (Remember that that means a graph which can be drawn on a plane with no edges crossing.) Suppose further that the graph has the property that from any vertex v, there is a path through the graph from v to v. Then that graph is called a *map*. For a map drawn on a plane, every edge is part of at least one cycle. The smallest possible cycles – that is, the cycles which are not bisected by any other edges of the graph – are called *countries* or *faces* of the graph. The face coloring problem assigns colors to the *faces* of a graph, so that no two faces that share an edge are the same color. There’s an extremely fascinating proof that any planar map can be face-colored with no more than four colors. We’ll talk about later – it’s the first computer assisted proof that I’m aware of.
Let’s talk a bit about graphs, being a tad more formal about them.
Set theory is, alas, going to need to take a break. I left my books on the train on friday. $200 worth of textbooks down the tubes, unless one of the conductors happened to hang on to them. At least I’ve got a pre-order already placed for a copy of the new addition of Ferreirós book; between that, and a new copy of Quine, I should be OK. But in the meantime, we’ll look at something else. Since I mentioned graph theory on friday, and I’ve been promising forever to write about it, I figured this is a good time.
My favorite introduction to graph theory is stolen from one of my grad school professors. It’s the first major use of what became graph theory, which is a proof by Euler.
Here’s the problem. Back in the 18th century, Euler lived in the city of Königsberg in Prussia. Königsberg is a city built around a fork in a river: it’s got parts of the city on the banks of the river, and parts on two islands. To get around
the city, there were seven bridges connecting the parts of the city. Is it possible to
take a trip through the city of Königsberg, crossing each bridge exactly once? More generally, given a city like Königsberg, how can you figure out whether it’s possible to tour the city crossing each bridge exactly once?