In a CPG (cubic planar graph), every vertex is 3-degree. Therefore there are
1.5 * V = E (edges) in a CPG. Per the Euler formula; ie,
(a) F (faces) = E(edges) - V(vertices) + 2. or
(b) F = 0.5 * V + 2
The dual of some CPG's is a fully triangulated planar graph; ie, a "triangulation",
or a T-graph. What kinds of CPG's have a T-graph dual? What kinds of CPG's exist.
There are three overt parameters which chaacterize a CPG. These are;
1. Three edge colorability
2. Connectivity (concerned with bridges)
3. Hamiltonian Circuit
A CPG with a bridge cannot have a HC and vice versa. The presence of an HC
guarantees 3-colorability. But does the lack of an HC absolutely preclude
3 edge colorability? That is the question that will be addressed in this paoer!
HYPOTHESIS:
1. Every CPG that has a T-graph dual is 3 edge colorable
2. Every CPG that is not 3 edge colorable does not have a T-graph dual
The face of the CPG becomes the vertex of its dual. The edges of the CPG
are edges in the dual. What about the vertices of the CPG? It is not likely
that they become the faces of the dual. So how are the dual's faces created?
Let's look at the metamorphisis of a graph as it becomes dualized.
A The face ABC disappears and the edges AB, BC & AC
2 /1\ ==> 2---1 collapse into the single edge {21). All 3 vertices
B---C are present in both 1 and 2.
A----B This CPG has 4 vertices and 4 faces. The faces are
|\ /| ABD (1), ACD (2), BCD (3) and the outer face (4)
| \/ | ==> There should be six edges in the dual;,ie.
| /\ | 12, 13, 14, 23, 24 & 34. The child is identical to
|/ \| the parent. The faces are 123 (F), 134 (G), 234 (H),
C----D 124 (I)
How do the original vertices, edges and faces map into the dual
1 2 3 4 12 13 14 23 24 34 123 134 234 124
A 1 1 1 1
1
This seems to be be a non fruitful endeavor. Let's try something else.
HYPOTHESIS: If a triangulation is involved, then the child is he dual of
the parent and the parent is the dual of the child.
LEMMA: If the hypothesis is true, then if the dual of a triangulation alway
has a Hamiltonian Circuit, then no CPG without a HC can have a triangulation
as a dual