Information Technology Reference
In-Depth Information
the resulting degree-2 vertices. This deletion and contractions give a charge
of +3.
(b) If the last degree-4 vertex is removed, and has no degree-four neighbors when
it is removed, then again its removal causes its neighbors to have degree 2
and is followed by four contractions, for a charge of +3.
(c) If, in the last removal of a degree-4 vertex, the vertex has one or more degree-
4 neighbors, then after this removal (and any ensuing edge contractions) the
graph becomes 3-regular. The next deletion will incur a charge of +1.
Thus, in all cases, the negative charge for the removal of a degree-4 vertex from
a 4-regular graph is balanced by a positive charge for a subsequent step of the
algorithm.
m/
5 is tight, for arbitrarily large graphs. In particular, the
graphs formed from
n/
5 disjoint copies of the complete graph
K
5
can have at
most
n
The bound
n
−
m/
5 vertices in any induced subgraph of treewidth at most 2, for
otherwise one of the copies of
K
5
would have only one of its vertices removed in
the subgraph, leaving a
K
4
subgraph which does not have treewidth 2.
The proof of Theorem 3 is similar in outline to this proof, but with a larger
set of cases and a more complex system of charges. We defer the details to the
full version of the paper [2].
−
5 No Very Large, Minor-Free Induced Subgraphs
In this section we prove Theorem 4. To prove this theorem, we begin with the
well-known result that
K
h
-minor free graphs are sparse [13,14,17,18].
Lemma 3 (Theorem 1.1 [18]).
Every simple K
h
-minor-free graph with n ver-
tices has O
(
nh
√
log
h
)
edges.
We will use this result to force the presence of a
K
h
minor even after deleting
many vertices. Lemma 4 allows us to densify a graph in terms of its girth (al-
lowing us to use Lemma 3 to argue the existence of a minor). We give a tighter
bound on the number of edges in a
K
h
-minor free graph with girth
g
in Corol-
lary 1. The proof of Theorem 4 may then be concluded by finding a family of
graphs that have suciently large girth.
Lemma 4.
Let G be a graph with n vertices, m edges, and su
ciently large
girth g. Then it has a minor G
that is a simple graph with n
≤
5
n
g
vertices and
n
+
n
edges.
m
−
Proof.
Let
T
be an arbitrary rooted spanning tree of
G
,let
r
be the root of
T
,
and let
V
i
be the set of vertices at
i
th
level of
T
.Let
=
g−
3
4
.Wechoosean
integer
a
such that
⊧
⊨
⊫
⊬
S
=
r
∪
V
a
+
k
(1)
⊩
⊭
k≥
0
