1--------------------------------------------2
B
1 <==--------3--------==>2
/|\
/ | \
/ | \
C / D | E \ F
/ | \
1 <==--------8-----9-----4---------==>2
/ \ I / \ K / \
G / H \ / J \ / L \ M
1 <==--------7----12-----10----5--------==>2
\ + O \ P / Q + /
N \ + \ / + / T
\ 11 /
\ R | S /
\ | /
\ | /
\ | /
\|/
1 <==--------6--------==>2
Figure 1 Original Triangulation
/-------------------A-------------------\
| | |
| |--------------B--------------| |
| | | |
| C---------D---------E---------F |
| | | | | |
| G----H----I----J----K----L----M |
| | | | | | |
| | O---------P---------Q | |
| | | | | |
\----N----R-------------------S----T----/
Figure 2. Cubic Dual of Figure 1
A
1 <==--------3
/|\
/ | \
/ | \
C / D | E \
/ | \
1 <==--------8-----9-----4
/ \ I / \ K / \
G / H \ / J \ / L \
1 <==--------7----12-----10----5
\ + O \ P / Q + /
N \ + \ / + /
\ 11 /
\ R | S /
\ | /
\ | /
\ | /
\|/
1 <==--------6
Figure 3: Figure 1 with vertex (2) removed
/--------------A-------------------\
|
| /
| C---------D---------E
| | | |
| G----H----I----J----K----L
| | | | |
| | O---------P---------Q
| | | |
\----N----R-------------------S
/-------------------A-------------------\
| | |
| |--------------B--------------| |
| | | |
| C---------D---------E---------F |
| | | | | |
| G----H----I----J----K----L----M |
| | | | | | |
| | O---------P---------Q | |
| | | | | |
\----N----R-------------------S----T----/
A
1--------------------------------------------2
B
1 <==--------3--------==>2
/ \
/ \
/ \
C / \ F
/ \
1 <==--------8 4---------==>2
/ \ \
G / H \ / J \ / L \ M
1 <==--------7----12-----10----5--------==>2
\ + O \ P / Q + /
N \ + \ / + / T
\ 11 /
\ R | S /
\ | /
\ | /
\ | /
\|/
1 <==--------6--------==>2
\ R | G /
\ [1] | [2] /
\------|-------/
| [6] / \ [8] |
| G / \ Y |
B [5] | / \ | [3] B
| / \ |
| / R \ |
|/ [7] \|
/-------------\
/ [4] \
/ Y \
Figure 1. Graph is 4-face colorable
In Figure 1, the face labels are in {}'s and the assigned colors
of each face are designated by the letters near the face labels.
Figure 1 is a subgraph of a larger graph; ie, graph G. By definition
graph G is a simple, loopless, fully triangulated planar graph,
ie, a 'triangulation'.
In Figure 2, the faces [6], [7] & [8] have been merged into the
pentagonal face, [9].
\ R | G /
\ [1] | [2] /
\------|-------/
| |
| |
B [5] | [9] | [3] B
| |
| |
| |
/-------------\
/ [4] \
/ Y \
Figure 2. Graph is not 4-face colorable