Information Technology Reference
In-Depth Information
If
b
has degree 2 and
c
has degree 3, then
c
is adjacent to a vertex
d
of degree at least 3
(otherwise
d
would be a degree 2 vertex not
belonging to a triangle). Delete
d
,isolating
triangle
abc
, and then apply case (
Δ
-a). This
incurs a total charge of at least +1
.
5.
d
c
a
(
Δ
-b)
b
a
c
(
Δ
-c) If
b
has degree 3 and
c
has degree at least 3, then delete
c
,add
a
and
b
to
S
and contract the edges incident to
b
. This incurs a charge of at least +0
.
5.
b
a
c
(
Δ
-d) If
b
has degree 4, then delete
b
,add
a
to
S
and contract
ac
. This incurs a charge of +0
.
5.
b
Vertex of degree 3 adjacent to a vertex of degree 4.
If there is a vertex
a
of degree 3 adjacent to a vertex
b
of degree 4, then we delete
b
. Deleting
b
incurs a net charge of
0
.
5, but reduces the degree of
a
to 2. Handling
a
as
above incurs a charge of at least +0
.
5, for a net charge of at least 0.
Vertex of degree 3.
If this is the first applicable case, then the graph must be
3-regular. Deleting any vertex
a
creates three vertices of degree 2 while incurring
achargeof
−
1
.
5. Processing the three resulting degree-2 vertices as above incurs
achargeofatleast+0
.
5 per degree-2 vertex, for a net charge of at least 0.
Vertex of degree 4.
If this is the first applicable case, then the graph must
be 4-regular. We consider the following cases for the subgraph
N
a
induced by
the neighbors
b,c,d,e
of a vertex
a
.
−
(a) If
N
a
has two non-adjacent pairs (
b,c
)and(
d, e
), then
a
,
b
,and
c
do not form
a triangle, so we can delete
d
and
e
, keep
b
and
c
,add
a
to
S
, and contract
ab
. This removes nine edges from the graph and deletes two vertices, for a
total charge of 0.
(b) If
N
a
is a star graph with center
b
, then consider the neighbors of
c
:
a,b,f,g
.
Neither
a
nor
b
can be adjacent to
f
or
g
, because otherwise they would have
too many neighbors. Thus we can process vertex
c
as in case (a) instead.
(c) If neither case (a) nor (b) applies, then
N
a
must contain a triangle. Without
loss of generality the triangle is formed by vertices
bcd
,so
a
is a vertex of a
tetrahedron (
K
4
) induced by vertices
a,b,c,d
. We may assume more strongly
that every vertex in the graph belongs to a tetrahedron, for if not we may
apply cases (a) or (b). We form four sub-subcases:
(i) If any connected component is a complete graph
K
5
, then deleting two
vertices leaves an isolated triangle and incurs a total charge of +1.
