Information Technology Reference
In-Depth Information
V
(
D
)
we have ch
3
(
A
)=
3
deg(
A
)
and for
Lemma 4.
For every vertex A
∈
every face f
∈
F
we have ch
3
(
f
)
≥
0
.
Proof.
(sketch) The first part of the claim follows from the first discharging step.
Let
f
be a face in
M
(
D
). Since
f
contributes at most 1
/
3 units of charge through
each of its edges, we have
ch
3
(
f
)
2
+
3
|
≥
3
|
f
|
V
(
f
)
|−
4. Therefore, if
|
f
|≥
6, then
ch
3
(
f
)
0. Recall that there are no faces of size two in
M
(
D
), thus, it remains
to consider faces of size three, four and five, i.e., triangles, quadrilaterals and
pentagons.
≥
Triangles.
Suppose that
0if
f
is not
a 1-triangle. If
f
is a 1-triangle, then we show that after Step 3(a) its charge is
at least
|
f
|
= 3. It is easy to show that
ch
3
(
f
)
≥
1
/
6, since it cannot have two bad neighbors (for otherwise, there is
an edge of
D
crossing four other edges). It then follows from Step 3(b) that the
final charge of
f
is zero.
−
Quadrilaterals.
Suppose that
|
f
|
= 4. A 0-quadrilateral does not contribute
|
V
(
f
)
|
=0wehave
ch
3
(
f
)=0.If
|
V
(
f
)
|≥
charge and therefore if
2, then
it is easy to see that
ch
3
(
f
)
≥
0. It remains to consider the case that
f
is a
1-quadrilateral. Observe that if
f
is a 1-quadrilateral and
ch
3
(
f
)
<
0, it must
be that
f
contribute 1
/
3 units of charge through precisely one of its edges in
Step 2, and 1
/
6 units of charge through each of its other edges. However, this
case implies that there is an edge of
D
that crosses four other edges (see Fig. 4
for an illustration).
2
+
3
|
Pentagons.
Suppose that
|
f
|
= 5. Recall that
ch
3
(
f
)
≥
3
|
f
|
V
(
f
)
|−
4.
Therefore, if
0, and it remains to consider the case
that
f
is a 0-pentagon. Recall that we may assume that the boundary of
f
consists of a simple 5-cycle. It follows from Lemma 2 that all the
D
-edges that
contain the
M
-edges of
f
are distinct. From this fact and Observation 3 one
concludes that it is impossible that
f
contributes charge through two of its
edges that are not consecutive on its boundary. Thus, if
ch
3
(
f
)
<
0, then
f
must
contribute 1
/
3 units of charge through two (consecutive) edges in Step 2 and
|
V
(
f
)
|≥
1, then
ch
3
(
f
)
≥
X
A
x
f
Y
y
z
Z
p
q
X
Q
Z
=
Y
Fig. 4.
If
f
is a 1-quadrilateral that contributes 1
/
3 units of charge through [
xy
]and
1
/
6 units of charge through each of [
Az
]and[
yz
], then (
Y
,Z
) crosses four edges
