**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 ,**

or

**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:

Post a Comment