Sunday, August 29, 2010

Undip codes and Euler's Formula

Any graph embedded in the sphere must obey Euler's formula:

F - E + V = 2 ,

where F, E, and V are the number of faces, edges, and vertices. Since every hamiltonian cubic graph embedded in the sphere has a valid undip codeword, a reasonable question is how (and whether) having a valid undip codeword can guarantee compliance with Euler's Formula.

Euler's formula is a bit simpler for cubic graphs. Cutting a cubic graph at every mid-edge, leaves a disconnected set of vertices, each still holding on to three half-edges. Thus,

E/V = 3/2 .

That fixed E/V ratio reduces Euler's formula for a cubic graph to

F - V/2 = 2 ,


F = V/2 + 2 .

In a valid the undip codeword there is one letter for each vertex. For every open letter, 'u' and 'n,' there is a matching close letter, 'd' and 'p'. Therefore a count of the occurrences of d and p, |d, p|, will count one half of the vertices:

|d,p| = V/2 .

Euler's formula then becomes

F = |d,p| + 2 .

It is easy to see that in weaving a valid undip codeword this rule is always obeyed. Each close letter, 'd' or 'p', completes a face, until we come to the final close letter. The final close letter also completes the hamilton cycle and thereby closes an additional face on both the left and the right-- that provides the final "+ 2" faces.

No comments: