Graph Decomposition and Turning Cycles

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.

So, for example, here is K5, and a decomposition of it into three subgraphs. To make it clearer, the original graph has its edges colored to match the colors of the vertices in the subgraph it belongs to in the decomposition.

i-6f81f2f02ca447ea05185bcd1251f2e0-k5-decomp.jpg

We can prove that any complete graph K2n+1 can be decomposed into n hamiltonian cycles. (As a reminder, a hamiltonion cycle is a path through a graph with the same first and last vertex, and which visits every other vertex in the graph exactly once.)

i-f10836b7af3364db663d9e155c1b7428-cycle-turning.jpg
The proof
is another turning proof. I'll just show you the basic structure of the hamiltonian cycle that we'll use, with K7 (2n+1 for n=3) as an example. You can see the cycle nice and clearly. If you turn the graph so that x is matched with 1, you get another cycle; if you turn again so that x is matched with 2, you'll get a third cycle. If you turn again, you'll get x matched with three - which is a repeat of the cycle we started with. In any complete graph with 2n+1 vertices, after n turns, you'll get a repeat. Further, we know that the complete graph for K2n+1 has (2n+1) choose 2 - or n×(2n+1) edges. Each hamiltonion cycle has 2n+1 edges, so there *can't* be more than N of them.

Using a simple variation of this, we can also show that any complete graph K2n
has N hamiltonian *paths*. (A hamiltonian path is a path that touches each vertex once, but it doesn't have to be a cycle.) The way we can prove that is really clever. Take the turning proof for 2n+1 and the hamiltonian cycles - and *delete* node x. Then it will produce N hamiltonian paths on a complete graph with 2n vertices.

More like this

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…
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…
One of the things that I find fascinating about graph theory is that it's so simple, and yet, it's got so much depth. Even when we're dealing with the simplest form of a graph - undirected graphs with no 1-cycles, there are questions that *seem* like that should be obvious, but which we don't know…
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…

Regrading the number of edges in a complete graph - K2n+1 has (2n+1) choose 2. Shouln't that be (2n+1) choose n. Nice example, thanks.

(2n+1) choose 2, because each edge uses two of the 2n+1 vertices - unless I'm very much mistaken.

You are correct, Morgan. You're trying to find every pair of vertices, so it's choose 2.

By Xanthir, FCD (not verified) on 07 Jul 2007 #permalink

Yep, thanks both. I didn't read the 'choose 2' part of the sentence in the context of its combinatorial meaning, which is obvious now. Instead, I read it as - for each vertex pick two with which to connect to.