Information Technology Reference
In-Depth Information
(ii) If two tetrahedra,
a,b,c,d
and
b,c,d,e
share triangle
b,c,d
without
forming a
K
5
,then
a
and
e
are non-adjacent. Deleting
a
and
e
removes
eight edges but leaves an isolated triangle (case
Δ
-a) for a net charge
of +2. We illustrate this case:
b
a
c
e
d
(iii) In the remaining cases all tetrahedra must be vertex-disjoint. If two
tetrahedra
abcd
and
efgh
are connected to each other by at least two
edges (
be
and
dg
), then we delete the two non-adjacent vertices
d
and
e
as illustrated here:
b
a
e
f
The dashed edges are possible con-
nections from vertices
a,c, f,h
.
g
c
d
h
1 but leaves two non-adjacent degree two
vertices (
b
and
g
) each of which can be processed via case (
Δ
-c), adding
charge +0
.
5 per vertex for a total charge of at least 0.
(iv) If every pair of tetrahedra are connected by at most one edge, then
contracting every tetrahedron to a vertex reduces the input graph to
a smaller 4-regular simple graph that necessarily contains a cycle of
three or more edges. In the uncontracted graph, this gives a cycle of
six or more edges that alternates between edges within tetrahedra and
edges outside the tetrahedra:
This incurs a charge of
−
In this case, we choose one of the tetrahedra of the cycle, and delete
the two vertices of this tetrahedron that do not belong to the cycle.
This removes seven edges from the graph for a net charge of
2, but
leaves two degree-2 vertices on a cycle of length at least 6. Each of
these may be processed as a degree-2 vertex that does not belong to a
triangle, giving a charge of +1 each and making the net charge be 0.
−
This case analysis concludes the proof of Theorem 1. The proof also gives
the outline for an ecient algorithm for finding an induced pseudoforest of size
at least
n
m/
4
.
5: after removing any high-degree vertices, form a data struc-
ture that lists the configurations of the graph obeying each of the cases in the
analysis. Because the remaining graph has bounded degree, selecting the first
applicable case, performing the reduction steps of the case, and updating the
−
