Information Technology Reference
In-Depth Information
contains at most
n
5
n
g
is a collection of vertices at every
th
level starting from level
a
along with root
r
.
Now we perform the following operation to obtain a minor
G
of
G
: for every
vertex
v
≤
S
vertices. Set
∈
G
\S
contract the edge
uv
where
u
is the parent of
v
in
T
.Thatis,
for every
v
=
a
+
k
, we contract
v
to its ancestor in
V
i−
1
.Since
the distance between two consecutive levels of vertices in
∈
V
i
,where
i
is
and the girth
of
G
is
g
, contracting these edges cannot result in self-loops or parallel edges.
Therefore
G
is simple.
Since we contract
n
S
n
edges, the number of edges in
G
is
−|S|
=
n
−
n
)=
m
n
+
n
.
m
−
(
n
−
−
Consider a graph
G
with
n
vertices, maximum degree 3, and girth
g
.If
G
has
n
+
ˉ
(
g
h
√
log
h
) edges, then, by Lemma 4,
G
has a minor
G
with
O
(
g
) vertices
and
ˉ
(
g
h
√
log
h
) edges. By Lemma 3,
G
is dense enough to have a
K
h
minor.
Therefore, we get:
Corollary 1.
Every simple K
h
-minor-free graph G with n vertices, maximum
degree
3
,andgirthg has n
+
O
(
g
h
√
log
h
)
edges.
ProofofTheorem4.
Let
G
=(
V,E
) be a 3-regular graph with
n
vertices,
m
=
3
2
edges and girth
ʩ
(log
n
); for example, the Ramanujan graphs have this
property [15]. In the following, we take
h
to be a constant. By Corollary 1,
G
has a
K
h
minor. Any subgraph
G
∗
(with
m
∗
edges and
n
∗
vertices) of
G
also
has girth
ʩ
(log
n
). By deleting
k
vertices, the best we can hope for is that we
delete 3
k
edges. That is,
m
∗
≥
3
k
. To ensure that
G
∗
does not have a
K
h
m
−
minor, we need
k
+
O
n
3
n
2
−
k
log
n
−
m
∗
≤
n
∗
+
O
(
n
∗
/g
)=
n
3
k
=
m
−
3
k
≤
−
Solving for
k
,werequirethat
1
4
−
O
(1
/
log
n
)
n.
k
≥
Substituting 2
m/
3for
n
gives the theorem.
Acknowledgments.
This material is based upon work supported by the Na-
tional Science Foundation under Grant Nos. CCF-1252833 and CCF-1228639
and by the Oce of Naval Research under Grant No. N00014-08-1-1015. The
authors thank Amir Nayyeri for helpful discussions.
