5Subcontraction, subdivision and linking
III Extremal Graph Theory
5 Subcontraction, subdivision and linking
We begin with some definitions.
Definition.
Let
G
be a graph,
e
=
xy
an edge. Then the graph
G/e
is the
graph formed from
G \{x, y}
by adding a new vertex joined to all neighbours of
x and y. We say this is the graph formed by contracting the edge e.
Definition
((Sub)contraction)
.
A contraction of
G
is a graph obtained by a
sequence of edge contractions. A subcontraction of
G
is a contraction of a
subgraph. We write G H if H is a subcontraction of G.
If
G H
, then
G
has disjoint vertex subsets
W
v
for each
v ∈ V
(
H
) such that
G
[
W
v
] is connected, and there is an edge of
G
between
W
u
and
W
v
if
w ∈ E
(
H
).
Definition
(Subdivision)
.
If
H
is a graph,
T H
stands for any graph obtained
from
H
by replacing its edges by vertex disjoint paths (i.e. we subdivide edges).
The
T
stands for “topological”, since the resulting graph has the same
topology.
Clearly, if G ⊇ T H, then G H.
Recall the following theorem:
Theorem
(Menger’s theorem)
.
Let
G
be a graph and
s
1
, . . . , s
k
, t
1
, . . . , t
k
be
distinct vertices. If
κ
(
G
)
≥ k
, then there exists
k
vertex disjoint paths from
{s
1
, . . . , s
k
} to {t
1
, . . . , t
k
}.
This is good, but not good enoguh. It would be nice if we can have paths
that join s
i
to t
i
, as opposed to joining s
i
to any element in {t
1
, . . . , t
k
}.
Definition
(
k
-linked graph)
.
We say
G
is
k
-linked if there exists vertex disjoint
s
i
-t
i
paths for 1 ≤ i ≤ k for any choice of these 2k vertices.
We want to understand how these three notions interact. There are some
obvious ways in which they interact. For example, it is not hard to see that
G ⊇ T K
t
if G is k-linked for some large k. Here is a kind of converse.
Lemma. If κ(G) ≥ 2k and G ⊇ T K
5k
, then G is k-linked.
Proof.
Let
B
be the set of “branch vertices” of
T K
5k
, i.e. the 5
k
vertices
joined by paths. By Menger’s theorem, there exists 2
k
vertex disjoint paths
joining
{s
1
, . . . , s
k
, t
1
, . . . , t
k
}
to
B
(note that these sets might intersect). We
say one of our 2
k
paths impinges on a path in
T K
5k
if it meets that path and
subsequently leaves it. Choose a set of 2
k
paths impinging minimally (counting
1 per impingement).
Let these join
{s
1
, . . . , t
k
}
to
{v
1
, . . . , v
2k
}
, where
B
=
{v
1
, . . . , v
5k
}
. Then
no path impinges on a path in
T K
5k
from
{v
1
, . . . , v
2k
}
to
{v
2k+1
, . . . , v
5k
}
.
Otherwise, pick the path impinging closest to
v
2k+j
, and reroute it to
v
2k+j
rather than to something in
{v
1
, . . . , v
2k
}
, reducing the number of impingements.
Hence each path (of any 2
k
) meet at most one path in
{v
1
, . . . , v
2k
}
to
{v
2k+1
, . . . , v
5k
} (once we hit it, we must stay there).
Thus, we may assume the paths from
{v
1
, . . . , v
2k
}
to
{v
4k+1
, . . . , v
5k
}
are
not met at all. Then we are done, since we can link up
v
j
to
v
k+j
via
v
4k+j
to
join s
j
to t
k
.
The argument can be improved to use T K
3k
.
Since we are doing extremal graph theory, we want to ask the following
question — how many edges do we need to guarantee G K
t
or G ⊇ T K
t
?
For two graphs
G
and
H
, we write
G
+
H
for the graph formed by taking the
disjoint union of
G
and
H
and then joining everything in
G
to everything in
H
.
Lemma.
If
e
(
G
)
≥ k|G|
, then there exists some
H
with
|H| ≤
2
k
and
δ
(
H
)
≥ k
such that G K
1
+ H.
Proof.
Consider the minimal subcontraction
G
0
of
G
among those that satisfy
e
(
G
0
)
≥ k|G
0
|
. Then we must in fact have
e
(
G
0
) =
k|G
0
|
, or else we can just
throw away an edge.
Since
e
(
G
0
) =
k|G
0
|
, it must be the case that
δ
(
G
0
)
≤
2
k
. Let
v
be of
minimum degree in
G
0
. and set
H
=
G
0
[Γ(
v
)]. Then
G K
1
+
H
and
|H| ≤
2
v
.
To see that
δ
(
H
)
≥ k
, suppose
u ∈ V
(
H
) = Γ(
v
). Then by minimality of
G
0
,
we have
e(G
0
/uv) ≤ k|G
0
| − k −1.
But the number of edges we kill when performing this contraction is exactly 1
plus the number of triangles containing
uv
. So
uv
lies in at least
k
triangles of
G
0
. In other words, δ(H) ≥ k.
By iterating this, we can find some subcontractions into K
t
.
Theorem. If t ≥ 3 and e(G) ≥ 2
t−3
|G|, then G K
t
.
Proof.
If
t
= 3, then
G
contains a cycle. So
G K
3
. If
t >
3, then
G K
1
+
H
where δ(H) ≥ 2
t−3
. So e(H) ≥ 2
t−4
|H| and (by induction) H K
t−1
.
We can prove similar results for the topological things.
Lemma.
If
δ
(
G
)
≥
2
k
, then
G
contains vertex disjoint subgraphs
H, J
with
δ(H) ≥ k, J connected, and every vertex in H has a neighbour in J.
If we contract J to a single vertex, then we get an H + K
1
.
Proof.
We may assume
G
is connected, or else we can replace
G
by a component.
Now pick a subgraph
J
maximal such that
J
is connected and
e
(
G/J
)
≥
k(|G|− |J| + 1). Note that any vertex could be used for J. So such a J exist.
Let
H
be the subgraph spanned by the vertices having a neighbour in
J
.
Note that if
v ∈ V
(
H
), then
v
has at least
k
neighbours in
H
. Indeed, when we
contract J ∪ {v}, maximality tells us
e(G/(J ∪{v})) ≤ k(|G| − |J| + 1) − k − 1,
and the number of edges we lose in the contraction is 1 plus the number of
neighbours of
v
(it is easier to think of this as a two-step process — first contract
J
, so that we get an
H
+
K
1
, then contract
v
with the vertex coming from
K
1
).
Again, we iterate this result.
Theorem.
Let
F
be a graph with
n
edges and no isolated vertices. If
δ
(
G
)
≥
2
n
,
then G ⊇ T F .
Proof.
If
n
= 1, then this is immediate. If
F
consists of
n
isolated edges, then
F ⊆ G
(in fact,
δ
(
G
)
≥
2
n −
1 is enough for this). Otherwise, pick an edge
e
which is not isolated. Then
F − e
has at most 1 isolated vertex. Apply the
previous lemma to
G
to obtain
H
with
δ
(
H
)
≥
2
n−1
. Find a copy of
T
(
F −e
)
in H (apart from the isolated vertex, if exists).
If
e
was just a leaf, then just add an edge (say to
J
). If not, just construct a
path going through J to act as e, since J is connected.
It is convenient to make the definition
c(t) = inf{c : e(G) ≥ c|G| ⇒ G K
t
}
t(t) = inf{c : e(G) ≥ c|G| ⇒ G ⊇ T K
t
}.
We can interpret the first result as saying
c
(
t
)
≤
2
t−3
. Moreover, note that if
e
(
G
)
≥ k|G|
, then
G
must contain a subgraph with
δ ≥ k
. Otherwise, we can
keep removing vertices of degree
< k
till we have none left, but still have a
positive number of edges, which is clearly nonsense. Hence, the second result
says t(t) ≤ 2
(
t
2
)
.
Likewise, we can define
f(k) = min{c : κ(G) ≥ c ⇒ G is k-linked}.
Since
κ
(
G
)
≥ c
implies
δ
(
G
)
≥ c
, the existence of
t
(
t
) and the beginning lemma
implies that f(k) exists.
In 1967, Mader showed
c
(
t
) =
t −
2 for
t ≤
7. Indeed, for
t ≤
7, we have the
exact result
ex(n; K
t
) = (t − 2)n −
t − 1
2
.
So for some time, people though c is linear. But in fact, c(t) is superlinear.
Lemma. We have
c(t) ≥ (α + o(1))t
p
log t.
To determine
α
, let
λ <
1 be the root to 1
− λ
+ 2
λ log λ
= 0. In fact
λ ≈
0
.
284.
Then
α =
1 − λ
2
p
log 1/λ
≈ 0.319.
Proof.
Consider a random graph
G
(
n, p
), where
p
is a constant to be chosen
later. So
G
(
n, p
) has
n
vertices and edges are chosen independently at random,
with probability
p
. Here we fix a
t
, and then try to find the best combination of
n and p to give the desired result.
A partition
V
1
, . . . , V
t
of
V
(
G
) is said to be complete if there is an edge
between
V
i
and
V
j
for all
i
and
j
. Note that having a complete partition is a
necessary, but not sufficient condition for having a
K
t
minor. So it suffices to
show that with probability > 0, there is no complete partition.
Writing
q
= 1
−p
, a given partition with
|V
i
|
=
n
i
is complete with probability
Y
i,j
(1 − q
n
i
n
j
) ≤ exp
−
X
i<j
q
n
i
n
j
≤ exp
−
t
2
Y
q
n
i
n
j
/
(
t
2
)
(AM-GM)
≤ exp
−
t
2
q
n
2
/t
2
.
The expected number of complete partitions is then
≤ t
n
exp
−
t
2
q
n
2
/t
2
,
As long as we restrict to the choices of n and q such that
t > n
s
log(1/q)
log n
,
we can bound this by
≤ exp
n log t −
t
2
1
n
= o(1)
in the limit t → ∞. We set
q = λ, n =
t
√
log t
p
log 1/λ
.
Then with probability
>
0, we can find a graph with only
o
(1) many complete
partitions, and by removing o(n) many edges, we have a graph with
p
n
2
− o(n) = (α + o(1))t
p
log t · n
many edges with no K
t
minor.
At this point, the obvious question to ask is — is
t
√
log t
the correct growth
rate? The answer is yes, and perhaps surprisingly, the proof is also probabilistic.
Before we prove that, we need the following lemma:
Lemma.
Let
k ∈ N
and
G
be a graph with
e
(
G
)
≥
11
k|G|
. Then there exists
some H with
|H| ≤ 11k + 2, 2δ(H) ≥ |H|+ 4k − 1
such that G H.
Proof.
We use our previous lemma as a starting point. Letting
`
= 11
k
, we know
that we can find H
1
such that
G K
1
+ H
1
,
with
|H
1
| ≤
2
`
and
δ
(
H
1
)
≥ `
. We shall improve the connectivity of this
H
1
at
the cost of throwing away some elements.
By divine inspiration, consider the constant
β ≈
0
.
37 defined by the equation
1 = β
1 +
log 2
β
,
and the function φ defined by
φ(F ) = β`
|F |
2
log
|F |
β`
+ 1
.
Now consider the set of graphs
C = {F : |F | ≥ β`, e(F ) ≥ φ(F )}.
Observe that H
1
∈ C, since δ(H
1
) ≥ ` and |H
1
| ≤ 2`.
Let H
2
be a subcontraction of H
1
, minimal with respect to C.
Since the complete graph of order
dβ`e
is not in
C
, as
φ >
β`
2
, the only
reason we are minimal is that we have hit the bound on the number of edges.
Thus, we must have
|H
2
| ≥ β` + 1, e(H
2
) = dφ(H
2
)e,
and
e(H
2
/uv) < φ(H
2
/uv)
for all edges uv of H
2
.
Choose a vertex
u ∈ H
2
of minimum degree, and put
H
3
=
H
2
[Γ(
u
)]. Then
we have
|H
3
| = δ(H
2
) ≤
2dφ(H
2
)e
|H
2
|
≤
β`
log
|H
2
|
β`
+ 1
+
2
|H
2
|
≤ `,
since β` ≤ |H
2
| ≤ 2`.
Let’s write b = β` and h = |H
2
|. Then by the usual argument, we have
2δ(H
3
) − |H
3
|
≥ 2(φ(H
2
) − φ(H
2
/uv) − 1) − |H
3
|
≥ bh
log
h
β
+ 1
− b(h − 1)
log
h − 1
b
+ 1
− b
log
h
b
+ 1
− 3
= b(h − 1) log
h
h − 1
− 3
> b − 4,
because h ≥ b + 1 and x log
1 +
1
x
> 1 −
1
x
for real x > 1. So
2δ(H
3
) − |H
3
| ≥ β` − 4 > 4k − 4.
If we put H = K
2
+ H
3
, then G H, |H| ≤ 11k + 2 and
2δ(H) − |H| ≥ 2δ(H
3
) − |H
3
| + 2 ≥ 4k − 1.
Theorem. We have
c(t) ≤ 7t
p
log t
if t is large.
The idea of the proof is as follows: First, we pick some
H
with
G H
such that
H
has high minimum degree, as given by the previous lemma. We
now randomly pick disjoint subsets
U
1
, . . . , U
2t
, and hope that they give us a
subcontraction to
K
t
. There are more sets that we need, because some of them
might be “bad”, in the sense that, for example, there might be no edges from
U
1
to
U
57
. However, since
H
has high minimum degree, the probability of being
bad is quite low, and with positive probability, we can find
t
subsets that have
an edge between any pair. While the
U
i
are not necessarily connected, this is
not a huge problem since
H
has so many edges that we can easily find paths
that connect the different vertices in U
i
.
Proof. For large t, we can choose k ∈ N so that
5.8t
p
log
2
t ≤ 11k ≤ 7t
p
log t.
Let
`
=
d
1
.
01
p
log
2
te
. Then
k ≥ t`/
2. We want to show that
G K
t
if
e(G) ≥ 11k|G|.
We already know that
G H
where
h
=
|H| ≤
11
k
+ 2, and 2
δ
(
H
)
≥
|H|+ 4k − 1. We show that H K
t
.
From now on, we work entirely in
H
. Note that any two adjacent vertices
have
≥
4
k
+1 common neighbours. Randomly select 2
t
disjoint
`
sets
U
1
, . . . , U
2t
in V (H). This is possible since we need 2t` vertices, and 2t` ≤ 4k.
Of course, we only need
t
many of those
`
sets, and we want to select the
ones that have some chance of being useful to us.
Fix a part
U
. For any vertex
v
(not necessarily in
U
), its degree is at least
h/
2. So the probability that
v
has no neighbour in
U
is at most
h/2
`
/
h
`
≤
2
−`
.
Write X(U) for the vertices having no neighbour in U, then E|X(U)| ≤ 2
−`
h.
We say
U
is bad if
|X
(
U
)
| >
8
·
2
−`
h
. Then by Markov’s inequality, the
probability that
U
is bad is
<
1
8
. Hence the expected number of bad sets amongst
U
1
, . . . , U
2t
is
≤
t
4
. By Markov again, the probability that there are more than
t
2
bad sets is <
1
2
.
We say a pair of sets (
U, U
0
) is bad if there is no
U − U
0
edge. Now the
probability that
U, U
0
is bad is
P
(
U
0
⊆ X
(
U
)). If we condition on the event that
U is good (i.e. not bad), then this probability is bounded by
8 · 2
−`
h
`
/
h − `
`
≤ 8
`
2
−`
2
1 +
`
h − `
`
≤ 8
`
2
−`
2
e
`
2
/(h−`)
≤ 9
`
2
−`
2
if
t
is large (hence
`
is slightly large and
h
is very large). We can then bound
this by
1
8t
.
Hence, the expected number of bad pairs (where one of them is good) is at
most
1
8t
2t
2
≤
t
4
.
So the probability that there are more than
t
2
such bad pairs is <
1
2
.
Now with positive probability,
U
1
, . . . , U
2t
has at most
t
2
bad sets and at
most
t
2
bad pairs amongst the good sets. Then we can find
t
many sets that are
pairwise good. We may wlog assume they are U
1
, . . . , U
t
.
Fixing such a choice
U
1
, . . . , U
t
, we now work deterministically. We would
be done if each
U
i
were connected, but they are not in general. However, we
can find
W
1
, . . . , W
t
in
V
(
H
)
\
(
U
1
∪ ···U
t
) such that
U
i
∪ W
i
is connected for
1 ≤ i ≤ t.
Indeed, if
U
i
=
{u
1
, . . . , u
`
}
, we pick a common neighbour of
u
j−1
and
u
j
if
u
j−1
u
j
6∈ E
(
H
), and put it in
W
i
. In total, this requires us to pick
≤ t`
distinct
vertices in
V
(
H
)
−
(
U
1
∪···∪U
t
), and we can do this because
u
j−1
and
u
j
have
at least 4k − t` ≥ t` common neighbours in this set.
It has been shown (2001) that equality holds in the previous lemma.
So we now understand
c
(
t
) quite well. How about subdivision and linking?
We decide to work on
f
(
k
) now, because Robertson and Seymour (1995) showed
that our first lemma that holds if
G T K
3k
instead of
G ⊇ K
3k
. We also know
how many edges we need to get a minor. Combining with our previous theorem,
we know
f(k) = O(k
p
log k).
We know we can’t do better than
k
, but we can get it down to order
k
by proving
our first lemma under the weaker hypothesis that G H where H is dense.
So far, we have proven theorems that say, roughly, “if
G
is a graph with
enough edges, then it subcontracts to some highly connected thing”. Now saying
that
G
subcontracts to some highly connected thing is equivalent to saying we
can find disjoint non-empty connected subgraphs
D
1
, . . . , D
m
such that each
D
i
is connected, and there are many edges between the
D
i
. The lemma we are
going to prove next says under certain conditions, we can choose the
D
i
in a
way that they contain certain prescribed points.
Definition
(
S
-cut)
.
Given
S ⊆ V
(
G
), an
S
-cut is a pair (
A, B
) of subsets of
the vertices such that
A ∪B
=
V
(
G
),
S ⊆ A
and
e
(
A \B, B \A
) = 0. The order
of the cut is |A ∩ B|.
We say (A, B) avoids C if A ∩ V (C) = ∅.
Example. For any S ⊆ A, the pair (A, V (G)) is an S-cut.
Lemma. Let d ≥ 0, k ≥ 2 and h ≥ d + b3k/2c be integers.
Let
G
be a graph,
S
=
{s
1
, . . . , s
k
} ⊆ V
(
G
). Suppose there exists disjoint
subgraphs C
1
, . . . , C
h
of G such that
(∗)
Each
C
i
is either connected, or each of its component meets
S
. Moreover,
each C
i
is adjacent to all but at most d of the C
j
, j 6= i not meeting S.
(†) Moreover, no S-cut of order < k avoids d + 1 of C
1
, . . . , C
h
.
Then G contains disjoint non-empty connected subgraphs D
1
, . . . , D
m
, where
m = h − bk/2c,
such that for 1
≤ i ≤ k
,
s
i
∈ D
i
, and
D
i
is adjacent to all but at most
d
of
D
k+1
, . . . , D
m
.
Proof.
Suppose the theorem is not true. Then there is a minimal counterexample
G (with minimality defined with respect to proper subgraphs).
We first show that we may assume
G
has no isolated vertices. If
v
is an
isolated vertex, and
v 6∈ S
, then we can simply apply the result to
G − v
. If
v ∈ S
, then the
S
-cut (
S, V
(
G
)
\{v}
) of order
k −
1 avoids
h − k ≥ d −
1 of the
C
i
’s.
Claim.
If (
A, B
) is an
S
-cut of order
k
avoiding
d
+ 1 many of the
C
i
’s, then
B = V (G) and A is discrete.
Indeed, given such an S-cut, we define
S
0
= A ∩ B
G
0
= G[B] − E(S
0
)
C
0
i
= C
i
∩ G
0
.
We now make a further claim:
Claim. (G
0
, S
0
, {C
0
i
}) satisfies the hypothesis of the lemma.
We shall assume this claim, and then come back to establishing the claim.
Assuming these claims, we show that
G
isn’t a countrexample after all. Since
(
G
0
, S
0
, {C
0
i
}
) satisfies the hypothesis of the lemma, by minimality, we can find
subgraphs
D
0
1
, . . . , D
0
m
in
G
0
that satisfy the conclusion of the lemma for
G
0
and
S
0
. Of course, these do not necessarily contain our
s
i
Assuming these claims, we
can construct the desired
D
i
. However, we can just add paths from
S
0
to the
s
i
.
Indeed,
G
[
A
] has no
S
-cut (
A
00
, B
00
) of order less than
k
with
S
0
⊆ B
00
, else
(
A
00
, B
00
∪ B
) is an
S
-cut of
G
of the forbidden kind, since
A
, and hence
A
00
avoids too many of the
C
i
. Hence by Menger’s theorem, there are vertex disjoint
paths
P
1
, . . . , P
k
in
G
[
A
] joining
s
i
to
s
0
i
(for some labelling of
S
0
). Then simply
take
D
i
= D
0
i
∪ P
i
.
To check that (
G
0
, S
0
, {C
0
i
}
) satisfy the hypothesis of the lemma, we first
need to show that the C
0
i
are non-empty.
If (
A, B
) avoids
C
j
, then by definition
C
j
∩ A
=
∅
. So
C
j
=
C
0
j
. By
assumption, there are
d
+ 1 many
C
j
’s for which this holds. Also, since these
don’t meet
S
, we know each
C
i
is adjacent to at least one of these
C
j
’s. So in
particular, C
0
i
is non-empty since C
0
i
⊇ C
i
∩ C
0
j
= C
i
∩ C
j
.
Let’s now check the conditions:
(∗)
For each
C
0
i
, consider its components. If there is some component that
does not meet
S
0
, then this component is contained in
B \A
. So this must
also be a component of
C
i
. But
C
i
is connected. So this component is
C
i
.
So C
0
i
= C
i
. Thus, either C
0
i
is connected, or all components meet S
0
.
Moreover, since any
C
0
j
not meeting
S
0
equals
C
j
, it follows that each
C
i
and so each
C
0
i
is adjacent to all but at most
d
of these
C
0
j
s. Therefore (
∗
)
holds.
(†)
If (
A
0
, B
0
) is an
S
0
-cut in
G
0
avoiding some
C
0
i
, then (
A ∪ A
0
, B
0
) is an
S
-cut of
G
of the same order, and it avoids
C
i
(since
C
0
i
doesn’t meet
S
0
,
and we have argued this implies
C
0
i
=
C
i
, and so
C
i
∩A
=
∅
). In particular,
no
S
0
-cut (
A
0
, B
0
) of
G
0
has order less than
k
and still avoids
d
+ 1 of
C
0
1
, . . . , C
0
h
.
We can now use our original claim. We know what
S
-cuts of order
k
loop
like, so we see that if there is an edge that does not join two
C
i
’s, then we
can contract the eedge to get a smaller counterexample. Recalling that
G
has
no isolated vertices, we see that in fact
V
(
G
) =
∪V
(
C
i
), and
|C
i
|
= 1 unless
C
i
⊆ S.
Let
C =
[
{V (C
i
) : |C
i
| ≥ 2}.
We claim that there is a set
I
of
|C|
independent edges meeting
C
. If not, by Hall’s
theorem, we can find
X ⊆ C
whose neighbourhood
Y
(in
V
(
G
)
− S
) such that
|Y | < |X|
. Then (
S ∪Y, V
(
G
)
−X
) is an
S
-cut of order
|S|−|X|
+
|Y | < |S|
=
k
avoiding ≥ |G| − |S|− |Y | many C
i
’s, and this is
≥ |G| − |S| − |X|+ 1 ≥ |G| − |C|− k + 1.
But
h ≤ |G| − |C|
+
|C|
2
, since
|G| − |C|
is the number of
C
i
’s of size 1, so we
can bound the above by
≥ h −
|C|
2
− k + 1 ≥ h −
3k
2
+ 1 ≥ d + 1.
This contradiction shows that I exists.
Now we can just write down the D
i
’s. For 1 ≤ i ≤ k, set D
i
to be s
i
if s
i
is
a C
`
with |C
`
| = 1, i.e. s
i
6∈ C. If s
i
∈ C, let D
i
be the edge of I meeting S
i
.
Let
D
k+1
, . . . , D
m
each be single vertices of
G −S −
(
ends of I
). Note those
exist because
≥ |G| − k − |C| ≥ h − b
3k
2
c
=
m − k
vertices are avaiable. Note
that each
D
i
contains a
C
`
with
|C
`
|
= 1. So each
D
i
is joined to all but
≤ d
many D
j
’s.
The point of this result is to prove the following theorem:
Theorem.
Let
G
be a graph with
κ
(
G
)
≥
2
k
and
e
(
G
)
≥
11
k|G|
. Then
G
is
k-linked. In particular, f(k) ≤ 22k.
Note that if κ(G) ≥ 22k then δ(G) ≥ 22k, so e(G) ≥ 11k|G|.
Proof.
We know that under these conditions,
G H
with
|H| ≤
11
k
+ 2 and
2δ(H) ≥ |H|+ 4k − 1. Let h = |H|, and d = h − 1 − δ(H). Note that
h = 2d − 2 + 2δ(H) − h ≥ 2d + 4k.
Let
C
1
, . . . , C
k
be connected subgraphs of
G
which contract to form
H
. Then
clearly each
C
i
is joined to all but at most
h −
1
− δ
(
H
) =
d
other
C
j
’s.
Now let
s
1
, . . . , s
k
, t
1
, . . . , t
k
be the vertices we want to link up. Let
S
=
{s
1
, . . . , s
k
, t
1
, . . . , t
k
}
. Observe that
G
has no
S
-cut of order
<
2
k
at all since
κ(G) ≥ 2k. So the conditions are satisfied, but with 2k instead of k.
So there are subgraphs
D
1
, . . . , D
m
, where
m
=
h −k ≥
2
d
+ 3
k
as described.
We may assume
s
i
∈ D
i
and
t
i
∈ D
k+i
. Note that for each pair (
D
i
, D
j
), we can
find
≥ m −
2
d ≥
3
k
other
D
`
such that
D
`
is joined to both
D
i
and
D
j
. So for
each
i
= 1
, . . . , k
, we can find an unused
D
`
not among
D
1
, . . . , D
2k
that we can
use to connect up D
i
and D
k+i
, hence s
i
and t
i
.
In 2004, the coefficient was reduced from 11 to 5. This shows
f
(
k
)
≤
10
k
. It
is known that f (1) = 3, f(2) = 6 and f(k) ≥ 3k − 2 for k ≥ 3.
Finally, we consider the function
t
(
t
). We begin by the following trivial
lemma:
Lemma. If δ(a) ≥ t
2
and G is
t+2
3
-linked, then G ⊇ T K
t
.
Proof.
Since
δ
(
G
)
≥ t
2
, we may pick vertices
v
1
, . . . , v
t
and sets
U
1
, . . . U
t
all
disjoint so that
|U
i
|
=
t −
1 and
v
i
is joined to
U
i
. Then
G −{v
1
, . . . , v
k
}
is still
t+2
2
−t
=
t
2
-linked. So
U
1
, . . . , U
t−1
may be joined with paths to form a
T K
t
in G.
To apply our previous theorem together with this lemma, we need the
following lemma:
Lemma.
Let
k, d ∈ N
with
k ≤
d+1
2
, and suppose
e
(
G
)
≥ d|G|
. Then
G
contains
a subgraph H with
e(H) = d|H|− kd + 1, δ(H) ≥ d + 1, κ(H) ≥ k.
Proof. Define
E
d,k
= {F ⊆ G : |F | ≥ d, e(F ) > d|F | − kd}.
We observe that
D ∈ E
d,k
, but
K
d
6∈ E
d,k
. Hence
|F | > d
for all
F ∈ E
d,k
. let
H
be a subgraph of
G
minimal with respect to
H ∈ E
d,k
. Then
e
(
H
) =
d|H|−kd
+1,
and δ(H) ≥ d + 1, else H −v ∈ E
d,k
for some v ∈ H.
We only have to worry about the connectivity condition. Suppose
S
is a
cutset of
H
. Let
C
be a component of
G − S
. Since
δ
(
h
)
≥ d
+ 1, we have
|C ∪ S| ≥ d + 2 and |H −C| ≥ d + 2.
Since neither C sup S nor H − C lies in that class, we have
e(C ∪ S) ≤ d|C ∪ S| − kd ≤ d|C|+ d|S|− kd
and
e(H − C) ≤ d|H| − d|C|− kd.
So we find that
e(H) ≤ d|H| + d|S| − 2kd.
But we know this is equal to d|H|− kd + 1. So we must have |S| ≥ k.
Theorem.
t
2
16
≤ t(t) ≤ 13
t + 1
2
.
Recall our previous upper bound was something like 2
t
2
. So this is an
improvement.
Proof.
The lower bound comes from (disjoint copies of)
K
t
2
/8,t
2
/8
. For the
uppper bound, write
d = 13
t + 1
2
, k = t · (t + 1).
Then we can find a subgraph H with δ(H) ≥ d + 1 and κ(H) ≥ k + 1.
Certainly |H| ≥ d + 2, and we know
e(H) ≥ d|H| − kd > (d − k)|H| ≥ 11
t + 1
2
|H|.
So we know H is
t+1
2
-linked, and so H ⊇ T K
t
.
So t(t) is, more or less, t
2
!