HYPOTHESIS: The dual of a cubic planar graph (CPG) is a triangulation (T-graph).
The dual of a T-graph is a CPG. If C is a CPG and G is a T-graph, and if
C is the dual of G, then G is the dual of C.
Let's use the Euler Formula; ie F = E-V+2, to determine if this mathematically
consistent. Let V_c = number of vertices in C; E_c = number of edges in C;
F_c = number of faces in C; V_g = vertices in G, E_g = edges in G & F_g = faces in G.
If the hypothesis is true, then
V_g = F_c; V_c = F_g
F_c = 1.5*V_c - V_c + 2.
F_c = 0.5*V_c + 2
F_g = E_g - V_g + 2, Given E_g = 3*V_g - 6, we have
F_g = 3*V_g - 6 - V_g + 2
F_g = 2*V_g - 4
From V_c = F_g, we have
V_c = 2*V_g - 4. and
V_g = 0.5*V_c + 2, Then
F_c = 0.5*V_c + 2 = 0.5*(2*V_g - 4) = V_g
F_g = 2*(0.5*V_c + 2) - 4 = V_c
Therefore, one necessary element in the dual <==> dual relationship is satisfied.
It is easy to show that C is the dual of G. It is more difficult to sshow that
G is the dual of C; except on a case by case basis.
SMALLEST CUBIC WITHOUT A HAMILTONIAN CIRCUIT.
|-------------------| |-------------------|
A------B------C-----D------E-----F------G------H
\ | / \ | /
\ | / \ | /
\ | / \ | /
\ | / \ | /
\ | / \ | /
\|/ \|/
J I
Figure 1
From this simple graph Hamiltonian-less cubic planar graphs of any order can
be constructed. Take any vertex and replace it with a ring of three vertices
Consider vertex J in Figure 1. Replace J with the ring JKL. Add edges BK
& CL. The result is
|-------------------| |-------------------|
A------B------C-----D------E-----F------G------H
| | | \ | /
| | | \ | /
| | | \ | /
J------K------L \ | /
\ / \ | /
\---------/ \|/
I
Figure 2
Is it possible to replace a 3-ring with a single vertex? How about the ring FGI?
No! FGI has only two external connections; ie, E and H. A 3-ring needs exactly
three external connections; for example ring JKL.
Does Figure 2 have a T-graph as a dual?
|-------------------| |-------------------|
| 1 | | 2 |
A------B------C-----D------E-----F------G------H
\ | / \ | /
\ 3 | 4 / 5 \ 6 | 7 /
\ | / \ | /
\ | / \ | /
\ | / \ | /
\|/ \|/
J I
Figure 3.
Figure 3 has seven faces, which is correct. But consider Face 5. Its border is
AJCDEFIHEDA. Note that edge DE forms two separate and distinct sections of the
border! Is this possible? NO!
THEOREM: A cubic with a bridge cannot have a dual