WIIIHIHINHIHHIHIWWWINHIIHHWHIIHHHI

   

 

 

 

 

 

 

 

 

 

llWillIlllilll’ﬁlilllﬂlllll

3 1293 00885 3263

 

 

This is to certify that the
dissertation entitled

PROBABILISTIC THRESHOLD FOR
COLLAPSIBILITY IN RANDOM GRAPHS

presented by
Joseph J. Spencer

has been accepted towards fulﬁllment
of the requirements for

Ph.D. degree in Mathematics

,‘ "" , , 7
fiéjﬁ 1’25 .~ (/ e/(L/v4 v

 

Major professor

{’6’ ”$34 / 77.?
Date ’

 

MS U is an Afﬁrmative Action/Equal Opportunity Institution 0-12771

PROBABILISTIC THRESHOLD FOR
COLLAPSIBILITY IN RANDOM GRAPHS

By

Joseph J. Spencer

A DISSERTATION

Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the Degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

1993

ABSTRACT

PROBABILISTIC THRESHOLD FOR COLLAPSIBILITY
IN RANDOM GRAPHS

BY

Joseph J. Spencer

A graph G is collapsible if for every subset S of V(G) with even cardinality, there
is a connected spanning subgraph H of G whose verticas of odd degree are precisely
the vertices of S. Collapsible graphs form an important class which satisfy the well-
known double cycle conjecture. We have determined the random graph threshold
function for this monotone property, i. e. we have found that a random graph with
minimum degree two is almost surely collapsible. Our approach makes use of the
theorem of Nash-Williams and Tutte which characterizes graphs with k edge-disjoint
spanning trees. This method can also be used to estimate the minimum number of

edges whose removal from a random graph leaves an eulerian subgraph.

DEDICATION

To my parents, Roy and Esther

iii

ACKNOWLEDGEMENTS

There are many people that I need to thank. They have all in one way or another
helped me through the years I have spent here at Michigan State. First and foremost
I would like to thank my advisor, Professor Ed Palmer, for all the guidance and
encouragement he has so patiently given me. I also would like to thank the members
of my thesis committee, Professor Sagan, Professor Plotkin, Professor Rotthaus and
Professor Esfahanian. Other faculty members that have had a positive inﬂuence on
me are Professor R. Phillips, Professor Sledd, Professor S. Schuur, and Professor Weil.
Next I would like to thank Barb Miller and Judi Miller who have done more than
just perform their jobs efficiently, they have become my friends. Finally I would like
to thank many of the graduate student who, over the years, have been my classmates
and my friends, Jose Giraldo, Peter Springer, Kathy Dempsey, Rick Hensh, Rick
Reynolds, Laura Reynolds, Bob Mckenzie, Rory Smith, Dawn Elzinga, Patti Bielak,
Lisa Hansen, Steve Smith, Jack Jordan, Margret Readdy, Mirjana Jovovic, Joan

Remski, John Clifford and anyone else that I have forgotten..

iv

Contents

LIST OF TABLES
Introduction

1 Collapsibility
1.1 Deﬁnitions .................................
1.2 Families of Collapsible Graphs ......................

1.3 Compulsory Threshold ..........................

2 Random Graphs
2.1 Probability Models ............................
2.2 Degree Distribution ............................
2.3 Relations Between Models ........................

2.4 Structural Properties ...........................

3 Edge-Disjoint Trees
3.1 The Theorem of Nash-Williams .....................

3.2 Edge Boundary Lemma ..........................

3.3 Threshold Theorem ............................

V

vii

12

12

14

16

18

24

30

32

3.4 Regular Graphs .............................. 37

3.5 Large Eulerian Subgraphs ........................ 39

BIBLIOGRAPHY 41

vi

List of Tables

1.1 Numbers of Collapsible and Supereulerian Graphs ........... 11

vii

Introduction

The theory of random graphs was founded over thirty years ago by Paul Erdos
and Alfred Rényi. In their fundamental papers [ErR59], [ErR60] and [ErR61] they
brought the theory of probability into play with graph theory and opened up an area
of investigation that has resulted in a thousand research papers, several books, two
journals and many special conferences. It is now regarded as a major component of
the field known as probabilistic combinatorics and has many important applications
especially in the analysis of algorithms from computer science. One of their most
interesting discoveries was the notion of the threshold function. The idea is that as a
graph accumulates edges at random, certain properties occur rather abruptly. Erdés
and Rényi found that they could predict quite accurately when such phenomena
transpired. It is much the same as chemical phase transition that occurs when a solid
such as ice is subjected to a gradual temperature increase and passes from solid to
liquid and then to gas. In this thesis we will determine sharp thresholds for graph
properties that arise in the study of the double cycle conjecture (DCC). See Jaeger

[Ja85] for a survey of this topic.

The DCC constitutes one of the best-known unsolved problems in graph theory.
It was ﬁrst raised by G. Szekeres [3273] and asserts that if G is a graph with no
bridges, then there is a multiset C of cycles in G such that each edge of G occurs in
exactly two members of the family C. The collapsible graphs originate in the work of

Paul Catlin and are an important set of graphs which satisfy the DCC. So too are the
l

supereulerian graphs. We first provide alternate deﬁnitions for collapsibility, relevant
characterization theorems, descriptions of some families of collapsible graphs and a
compulsory threshold. Then we introduce several probability models, discuss their
relationships and give detailed proofs of important structural properties of random
graphs. Next the decomposition theorem of Nash-Williams is presented. Together
with our edge boundary lemma, it can be applied to obtain the threshold for edge-
disjoint spanning trees and consequently the threshold for collapsibility. Finally we are
able to use our techniques to estimate the size of large eulerian subgraphs in random
graphs. During the course of our investigation several difﬁcult unsolved problems
arise. First there is the enumeration problem for collapsible graphs. Then we have
the problem of determining an efﬁcient algorithm for ﬁnding edge-disjoint spanning
trees in random graphs with minimum degree two. Finally there is the question of

the asymptotic probability of collapsibility for cubic graphs.

Here are some of the basic deﬁnitions we need from graph theory. Those not
included may be found in the books [B085] and [Pa85]. A graph G consists of a ﬁnite
set of vertices, V(G), together with a set of edges, E(G), which are unordered pairs
of vertices. The cardinality of V(G) is the order of G and the cardinality of E(G) is
the size of G. We will use the convention that n = |V(G)|. If 11,2) 6 V(G) and the
edge e = {u,v} we say u and v are incident with e or that e is incident with v. If u
and v are both incident with the edge e, we say that u and v are adjacent. We also
say that e joins u and v. The degree of a vertex v, denoted by degG(v), is the number
of edges that are incident with v in G. A multigraph is a graph in which any ﬁnite

number of edges between two vertices is allowed.

The vertex neighborhood of a set S' Q V(G) is deﬁned by

N(S) = {v | v ¢ Sis adjacent to some u 6 S}.

For a singleton set, we will use N (v) = N ( {0}) A walk in a graph G is a sequence
of vertices v1,vg, . . . ,1)... such that v.- is adjacent to 1),“, i = 1 to m — 1. If vl = vm,
the walk is closed. A path in G is a walk in which no vertex is repeated. The length
of a path is number of edges in it. A graph G is connected if there is a path between
every pair of vertices. The distance between two vertices is the length of a shortest

path between them.

A cycle is a walk with at least three vertices in which the ﬁrst and last vertices
are the only ones repeated. A graph is acyclic if it contains no cycles. A tree is a
connected, acyclic graph. A graph that is a path with n vertices and n — 1 edges will
be denoted by P“. We denote a cycle of order n by C... A graph with n vertices and all
(’2‘) possible edges is called the complete graph and is denoted by Kn. The cartesian
product or product of the graphs G and H, G x H, is the graph whose vertices are all
ordered pairs (u, v), where u 6 V(G) and v E V(H). The edges of G x H join (111,121)
and (212,122) if (i) u; = 112 and v1 is adjacent to v; or (ii) v1 = v; and u; is adjacent
to U2. For m 2 1 the m-cube Qm is K2 x . . . x K2, where the number of factors is m.

We see that Q1 = P1 and Q2 = C4.

A subgraph H of G is a graph with V(H) Q V(G) and E(H) is a subset of those
edges in E (G) that are incident with with only the vertices in V(H). We will use the
notation H E G to mean that H is a subgraph of G and V(H) = V(G). An induced
subgraph H of G is a subgraph such that if 21,2) 6 V(H) and {u,v} is and edge of G
then {u, v} is also and edge of H. For a set X C V(G), X " will represent the induced
subgraph whose vertex set is X. A subgraph H of G spans G if V(H) = V(G). A
maximal, connected subgraph is called a component. An edge whose removal from a
graph increases the number of components is called a bridge. A graph G is eulerian
if there exists a closed spanning walk that includes each edge of G exactly once. A

graph is supereulerian if it has a spanning eulerian subgraph.

Let g, be the set of all 2(3) labeled graphs of order n. A subset Q of 9,, is a graph
property if it is closed under isomorphism. A graph property Q is a monotone graph
property or monotone if for any graph H that has Q, all graphs G such that H C_: G

also have Q.

We will often use a right arrow “—i” mean the limit as n goes to co.

Chapter 1

Collapsibility

1 .1 Deﬁnitions

A graph G is collapsible (see [Ca88a]) if for every subset S of V(G) with even
cardinality, there is a connected spanning subgraph H of G in which 5' is the set
of odd vertices in H. We shall refer to this as “deﬁnition one” for collapsibility. It
is equivalent that a graph G is collapsible if for every subset S of V(G) with even
cardinality, there is a subgraph P such that G — E(I‘) is connected and v E S' if and
only if the degree of v in F is odd. We call this “deﬁnition two”. We will also consider
K1 to be collapsible. The cycle 03 is an example of a collapsible graph while C4 is
not collapsible. More examples will follow later. In this section we will describe some

of the properties of collapsible graphs.

For a graph G with a subgraph H, the contraction G/H is the multigraph ob-
tained from G by identifying H with a single vertex v”. Thus G/ H has vertices
V(G/H) = [V(G) — V(H)] U {v3} and lE(G/H)| = |E(G)| — IE(H)|. Note that all
edges connecting V(G) — V(H) to V(H) are included in G/H. Multiple edges can
arise when a vertex in N (V(H )) is adjacent to two or more vertices of H. We are

now ready to state a very useful result for the identiﬁcation of collapsible graphs.

Theorem 1.1.1 ([Ca88a]) Let H be a collapsible subgraph of G. Then G is col-
5

lapsible if and only if G/H is collapsible.

As a result of this theorem, we can sometimes determine whether or not a graph
G is collapsible by performing a series of contractions. Thus G is collapsible if it can
be reduced to a single vertex. But we also have the following important sufﬁcient

condition for a graph to be collapsible.

Theorem 1.1.2 ([Ca88a]) If a graph has two edge-disjoint spanning trees then it is

collapsible.

‘Proof: This can be shown directly from “deﬁnition one” of collapsibility. Let G
be a graph with two edge disjoint spanning trees and let S be an even ordered subset
of V(G). We wish to construct a spanning subgraph H where vertices of odd degree
are precisely the vertices in 5. There are four kinds of vertices depending on their

parity in G and their desired parity in H. Let

A = {v | degG(v) is even and degH(v) is even},

B = {v | degG(v) is even and degy(v) is odd},

C = {v I degG(v) is odd and degy(v) is even}
and

D = {v I degg(v) is odd and degy(v) is odd}.

Note that BUD = S. The vertices in B and C must have their parities changed.
Since IE I + IDI and ICI + |D| count the number of odd vertices in a graph, they are
both even integers. It follows that IBI + IC I + 2|D| is also an even integer. Thus
[8 I + IC I, the number of vertices that must have their parities different in H and G,

is even. We arbitrarily pair up the vertices that must have their parity changed and

consider the paths that connect them in one of the spanning trees. By removing the
symmetric differences of these paths, we create a graph H in which the vertices of
S are exactly those of odd degree. The existence of the second spanning tree of G

guarantees that H is a connected subgraph. I

We can see directly from the “deﬁnition one” that all collapsible graphs are su-
pereulerian. One simply chooses .S' to be the empty set. Here is another interesting

trait of collapsible graphs.

Theorem 1.1.3 ([Ca88a]) Let G be a graph with a collapsible subgraph H. Then

G is supereulerian if and only if G / H is supereulerian.

This theorem shows how collapsibility can be used to help us identify supereulerian

graphs. Supereulerian graphs are an important class of graphs which are known to

satisfy the DCC.

1.2 Families of Collapsible Graphs

In this section we will give examples of collapsible graphs as well as examples of

non-collapsible graphs. Certain families of collapsible graphs will be described.

Let G be any collapsible graph with IV (C )I Z 2. Consider the cartesian product of
G with any connected graph H. Since G is collapsible, we may contract each copy of
G in G x H to a single vertex, resulting in a graph we shall call Hg. Clearly the graph
HG can be obtained from the graph H by replacing every single edge in H by |V(G)I
multiple edges. Thus we have |V(HG)I = |V(H)| and IE(HG)I = IE(H)||V(G)I. Since
two vertices with two or more edges joining them form a collapsible graph, we may,
by a series of contractions, reduce HG to a single vertex. Thus it is collapsible and so

ultimately G x H is also collapsible.

We now need another reduction method which Catlin has described in [Ca88b].
Let G be a graph containing the induced four cycle C which has vertices w, 1:, y and z
and edges {w,a:}, {:c,y}, {y, z}, and {2, w}. The reduction 1r is made by eliminating
the edges of the cycle and then identifying the non-adjacent pairs of vertices and
adding an edge between the two resulting new vertices. If 121 is the identiﬁcation of
w and y and v; is the identiﬁcation of a: and 2, we keep all edges not in C, including
multiple edges that may arise, and add the edge {111, v2}. We will call the reduced

graph G/n.

Theorem 1.2.1 ([Ca88b]) Let C be an induced four cycle in the graph G. If G/7r

is collapsible then G is collapsible.

Now we may consider the m-cube Qm-. The graphs Q1 and Q2 are not collapsible.
But we can show Q, is collapsible by performing two 1r reductions and then use
contractions to obtain a single vertex. It can easily be shown by induction that Qm

for m _>_ 4 is also collapsible.

Next let us next consider the cartesian product of paths, which we will call a
lattice. We ﬁnd that the lattices of the form P1 x Pm, m 2 1, are not collapsible.
These lattices have no spanning connected subgraphs with the four corners as the
only vertices of odd degree. Also the lattice P; x P2 is not collapsible. If we take
5 to be a set of eight vertices, leaving out only one of the middle side vertices, we
cannot find a connected spanning graph with the vertices in 5 having odd degree. It
is easily shown by a series of 7r reductions that P; x R; is collapsible. Using induction,
it follows that all lattices P; x Pm with l 2 2 and m 2 3 are collapsible. Here we have

found two non-collapsible graphs whose cartesian product is collapsible.

Another family of collapsible graphs consists of the cartesian products of cycles,

G; x Gm. If I = 3, then one of the cycles is a triangle, so the cartesian product

is collapsible, as shown above. If both l,m 2 4, then the lattice 131-1 x Pm_1 is a
collapsible spanning subgraph, so the graph G: x C... is collapsible. Using 7r reductions

it is easily seen that the set of graphs of the form K 2 x Cn are also collapsible.

The well-known Petersen graph may described as a ﬁve pointed star inside a
pentagon with each point of the star connected to the corresponding vertex of the

pentagon. Here is a more precise description. Let the vertex set be
{1,2,3,4,5,a,b,c,d,e}
and the edge set be

{ {1,2}.{2.3}.{3.4},{4.5},{5.1}.{c.b}.{b.c}.{c.d}.
{d, e}, {e,a}, {1,a}, {2,d}, {3, b}, {4,6}, {5,6} }.

This is the smallest bridgeless graph with minimum degree three that is not collapsi-

ble.

The Augmented Petersen graph is constructed from the Petersen graph by adding
one vertex on the edge between 1 and 2 and one vertex on the edge between b and
c and then connecting these two new vertices with an edge. According to Zhi-Hong
Chen of Wayne State University (email communication) it is not known if this graph

is collapsible.

1.3 Compulsory Threshold

Consider a monotone graph property Q. Suppose every graph with n vertices and
at least Mn edges has property Q. Let us assume that M... is the least such value.
Then Mn is called a compulsory threshold for property Q. In this section we will ﬁnd

the compulsory threshold for collapsibility. First we need two lemmas.

10

Lemma 1.3.1 Let Q be the graph property that every edge is in a triangle. Then the
n — l
2
( 2 l +

Proof: Consider the graph with vertex set {1, 2, . . . , n} which consists of a complete

compulsory threshold for Q is

forn Z 3.

graph K -1 on the ﬁrst 72 - 1 vertices and also has the edge e joining vertex n -— 1
71—1

with vertex n. This graph has ( 2 ) + 1 edges but e is not in a triangle. Therefore

the compulsory threshold is at least (”131) + 2.

Consider a complete graph Kn, n 2 3. Each edge of Kn belongs to n — 2 triangles,

so removal from Kn of any n — 3 edges will result in a graph that has property Q.

12 71—1

any graph with ('31) + 2 edges will have property Q. I

Since

Our second lemma follows from a theorem of Catlin.

Theorem 1.3.2 ([Ca88a]) Let H1 and H; be subgraphs of H such that V(H) =
V(H1)UV(H2), E(H) = E(H])UE(H2) and V(H1)nV(H2) # 0. IfH1 and H2 are

collapsible, then so is H.

Lemma 1.3.3 If G is a connected graph in which every edge is in a collapsible sub-

graph of G, then G is collapsible.
Proof: By repeatedly applying Theorem 1.3.2, we see that G is collapsible.-

Theorem 1.3.4 The compulsory threshold for collapsibility for a graph with n ver-

Inf)”

tices is

11

forn Z 3.

Proof: Consider the graph G of order n and size ("31) + 1 described in the proof
of Lemma 1.3.1. Let H be the subgraph isomorphic to K -1. Then G/H = K2. Since

H is collapsible but K 2 is not, it follows from Theorem 1.1.1 that G is not collapsible.

We know from Lemma 1.3.1 that every edge in a graph with (”'24) + 2 edges is in
a triangle, which is a collapsible graph. So by Lemma 1.3.3 a graph with (7:1) + 2

edges is always collapsible. I

The enumeration of collapsible and and supereulerian graphs constitutes an un-
solved problem. For graphs with a small number of vertices we have generated the

following numbers for the labeled and unlabeled cases.
Table 1.1: Numbers of Collapsible and Supereulerian Graphs
Collapsible Su erian
l
0
1

10

 

1 1
0 0
1 1
7 3
3

21 10

Chapter 2

Random Graphs

2.1 Probability Models

In this section we will describe three probability models commonly used in the
study of random graphs and give a simple illustration of how each model is used.

They will be called Model A, Model B and Model C.

In Model A, the sample space consists of all labeled graphs with n vertices. Given

a number 0 < p < 1, the probability of a graph G with M edges is deﬁned by
13(0): PM(1- PlN’M

where N = ('2‘), the number of unordered pairs of vertices. The number p is the
edge probability. Thus the sample space consists of Bernoulli trials and the edges
are selected independently with probability p. Note that when p = 1/2, every graph

with n vertices has equal probability. In Model A, the expected number of vertices

n (n ; 1)p2(1 — p)”’3.

In Model B, the sample space consists of all labeled graphs with n vertices and M

of degree two is

edges. For a given value M, O S M S N, the probability of a graph G is defined by

13

In Model B the expected number of isolated vertices in a graph is

(_<__:e;‘>>
(<7)

In Model C the sample space for a given n and r, 1 _<_ r < n, consists of all digraphs
with every vertex having outdegree r. This model is sometimes called “r—out”. Each
digraph D has probability

P(D) = (17...

13-]
r

For a digraph in Model C, the expected number of vertices with indegree zero is

By ignoring the orientation of the edges and consolidating multiple edges another

sample space consisting of graphs is created.

In the study of random graphs, we can conclude nothing about any one graph,
what we do study are properties of sets of graphs. If Q is some property of graphs
and A is the set of graphs of order n with property Q, and P(.A) -—> 1 as n —-> 00,
then we say almost all graphs have property Q or the random graph has property Q
almost surely (a. 3.). We are studying a sequence of sample spaces and the limit of a

sequence of probabilities.

An important discovery of Erdbs is the notion of the threshold function for certain
properties of random graphs. In Model A we express the edge probability p as a
function of the number of vertices n, i. e. p = p(n). The function p“(n) is a threshold

function for a graph property Q if

p(n)/p"‘(n) —+ 0 implies that almost no G has Q

l4

and

p(n)/p’(n) —» 00 implies that almost every G has Q.

We may similarly deﬁne threshold functions in Model B by considering M = M (n)
It has been observed by Bollobas and Thomason that every monotone graph property

has a threshold function [BoT86I.

The ﬁrst moment method is an important tool from probability theory that is used

frequently in the study of random graphs. Suppose X is a nonnegative integer valued
random variable, then EIX] _>_ P(X 2 1). Thus if EIX] -—* 0, then P(X Z 1) —) 0

and therefore P(X = 0) —» 1. So, for example, if

X = the number of vertices of degree 0 in a random graph

 

and
pzzlorgln,
then
Em = n<1—pr-‘ (2.1)
S nexp(—p(n-1)) (2-2)
s nexp(—2logn)exp(p) (2.3)
S n(n‘2)exp(P)-*0o (24)

Thus P(X = 0) ——> 0 and we may conclude that if p = 21353, then a random graph in

Model A almost surely has no vertices of degree zero.

2.2 Degree Distribution

Having minimum degree at least k is a monotone graph property. It has a well
known sharp threshold function. If

p— logn-I—(k-1)]oglogn+wn

‘n

 

(2.5)

15

where w" -+ 00 and 1.12,. = o(log log n), then a random graph almost surely has mini-

mum degree lc.

Let us look at equation (2.5) with k = 2 and see how each term affects the degree
of a random graph. Let X.- be the random variable that counts the number of vertices

of degree i in a random graph. Then the expected number of vertices of degree two
is given by

E [X2] = n (n g 2)P’(1 - p)"”- (2-6)

First let us look at p = 1353. We have

 

3 o n 2
EIXg] = (1+0(1))%(l i ) e‘”" (2.7)
= (1+ 0(1))____”(1°§")2%_. 00 (2.8)

But this is not the threshold for minimum degree two because the expected number

of vertices with degree one is

Em = n(" ;‘ 1)pu — p)“ (2.9)
2 (1+ 0(1))n210—1g12%—+ oo. (2.10)

In fact we ﬁnd that E[X.-] —> 00 for all i _>_ 1.

 

 

 

If
__ logn + log logn
p— n
then
_ n(logn)2 l
E[X2] _ (1+o(1)) 2 ”logn (2.11)
l
= (1+0(1))0gn—>oo- (2.12)

16

but

 

E[X1]=(1+o( 171)) 21°“ 7400

n nlogn

Adding the factor (on with can —» 00 and 1.12,, = o(log log n) forces E [X 1] —2 0 while not

interfering with the behavoir of E [X2].

2.3 Relations Between Models

Usually we ﬁnd that it is more straightforward to work with Model A than Model
B. Fortunately these two models are very closely related and it is often easy to convert
results from one to the other. In this section a random graph in Model A with n
vertices and edge probability p will be represented by GM, and its set of edges by
Emp. A random graph in Model B with n vertices and M edges will be represented
by GmM' A graph property Q is convex if G1 (_3 G2 and G1 and G2 both have Q
implies that any H such that G1 Q H Q G2 also has Q. For a convex graph property

we have the following well-known conversion theorem.

Theorem 2.3.1 ([3079]) Let 0 < p = p(n) < 1 be such that pn2 -> 00 and

(l -- p)n2 -» 00 as n —+ 00 and let Q be a property of graphs.

(i) Suppose e > 0 is filed and, if(1 —- e)pN < M < (1+ c)pN, then GmM has Q

almost surely. Then G",p has Q almost surely.

(ii) If Q is a convex property and GM, has Q almost surely then GmLpNJ has Q

almost surely.

For a graph property Q that is not convex we have the following method of
conversion from Model A to Model B that is presented in [BoFF87]. Note that at
times we will use non-integral quantities that ought to be rounded up or down. It

should be clear that this practice will not affect the results.

17

Lemma 2.3.2 ([BoFF87]) Let Q be any graph property and suppose M = pN. If
nP(G,,,p has Q) —» 0 as n -+ 00

then

P(GmM has Q) —-+ O as n —> 00.

Proof: First note that

P(lEn.pl = M) = (13);)“(1 — PlN-M- (2.13)

Now using Stirling’s formula and the fact that M = pN, we can show that

 

 

 

1
P(IEMI = M) 2 (1 — 0(1))m. (2.14)
Also, using equation (2.13) we ﬁnd that

P G”, h Q (1 En, = M

P(Gn, has Q | |E..,,,| = M) = ( P PaflE ail—I114)” ) (2.15)
‘71,? —
M _ N—M
(1")le — p)”-M

= P(GmM has Q). (2.17)

Now clearly it follows from the deﬁnition of Model A and from (2.17) that

P(GM has Q) = ZP(G,,,p has Q | IBM] = M')P(IE,,,,,| = M’) (2.18)
Ml

= E P(G’mM. has Q)P(|E,,,,| = M’). (2.19)
M!

By using a single summand of the right hand side of (2.19), say when M’ = M, we

see

P(GM, has Q) 2 P(GW has Q)P(|E.,,,| = M) (2.20)

18

But now with equation (2.14) and using that N is asymptotic to 722/2,

P(Gw has Q) 2 (1 _ 0(1))(/;:3P(G,,M has Q). (2.21)

Thus
nP(G,,,p has Q) 2 (1 — o(l))\/;P(Gn,u has Q)

and our result is proven. I

2.4 Structural Properties

We are interested in random graphs with edge probability p roughly equal to
log n/n. The average degree of the vertices of such a graph is about log n. We need
to know that vertices of low degree are not too close to each other in a random
graph and that there are not too many of these. These structural properties will be
needed to help us show that in random graphs, small sets of vertices have large edge
boundaries and to show the existence of edge-disjoint trees in random graphs. We let
d = pn, and we say that v is small its degree is less than 2%, otherwise we say v is
large. In [BoFF87] the authors gave only a sketch of the proof of the next theorem,
but here we shall include more details. As in [BoFF 87] the proof will be given for

both Models A and B.

Theorem 2.4.1 ([BoFF87]) In Model A with edge probability

 

p _>. logn (2.22)
n
or in Model B with
M _>_ énlogn (2.23)

the following statements for a random graph G hold almost surely:

. l .
(a) G contains no more than n3 small vertices.

19

(b) G does not contain two small vertices at a distance offour or less apart.

Proof: (a) Let Q, be the property that a random graph G has more than ni small
vertices. We would like to show that almost all graphs do not have this property.
Let X count the number of sets containing ni small vertices. We know from the ﬁrst

moment method that

P(Gn, has Q.) g E[X]. (2.24)

For each vertex v in a set S of order 3 consisting of only small vertices, the number
of edges joining v to vertices not in S will be (”F’) for 0 S i S 2‘1—0. Each of the edges
occurs with probability p and each non-edge with probability 1— p. So the probability

that a given 5' consists of small vertices is bounded by

If): (n : 8) p‘(1 — p)"““] s. (2.25)

i=0

So the expected number of sets 5 of small vertices with IS I = s will be

EIX] S (Z) If (n:s)p‘(1-p)"”“I - (226)

Now using the facts that IS I = ni and p _>_ “-53 along with the bound for the tail of

a binomial distribution (see [Pa85] page 133) we see

it n—s d d 71-3—1 8
Em S (ll(d/20)PT°(1—p)“"'ﬁp( 20“) (2.27)

 

s p(n — s + 1) — 2%
s Q): [0(1)(20e9;—8p)d/2°exp(—pn + ps + 313)] (2.28)

S [0(1):Z exp(24—Od) exp(—d + ps + dp/20)I 8 (2.29)

20

.i
g [0(1)n§exp(—-;—3d)] (2.30)
. .11
g [0(1)n3exp(—-2d/3)exp(—5d/60)I (2.31)
S 0(l)exp(—-1-1§dn'1’). (2.32)

Because if = np 2 log n, clearly exp(—1—1§dn‘i) —2 0 as n —2 0. Thus P(Gndp has Qa) —+

0 and so almost surely GM, has fewer than ni small vertices.

This result is easily converted to Model B as follows. Multiply both sides of
inequality (2.32) by n and we see that nexp(—-11—2dn?15) —2 0 as n ——> 00. It follows from

Lemma 2.3.2 that almost surely Qa does not hold in Model B.

(b) Let Qb be the property that there exist two small vertices at a distance of four
of less apart. We would like to show that this property does not hold almost surely.
Let X count the number of pairs of small vertices at a distance of four or less apart.

Then

P(GM, has Q) _<_ E[X]. (2.33)

The expected value of X is bounded by the expected number sets of two small vertices
multiplied by the probability that the two vertices have a path of length four or less

between them. So we multiply inequality (2.26) by nap4 + n2p3 + np2 + p to obtain

i=0

d/20 2
_ 2 . .
E[Xl S (g) [E (n z. )p'(1 - p)"""] (72317“ + 122133 + 1w2 + p) - (2-34)
Using the same estimates as in part (a) for s = 2, we ﬁnd
P(Gmp has Qb) _<_ n5p4e‘l‘5“. (2.35)

Since d 2 logn we see that P(Gnm has Q5) —+ 0. Therefore in Model A we know that

aJmost surely there are not two small vertices at a distance of four or less apart.

21

Now for Model B. If p 2 93333 then d 2 210g n. Multipling inequality (2.35) by n
we ﬁnd that

12(125p‘e'1‘5") S n6p4n‘3 —> 0 (2.36)

and thus by Lemma 2.3.2 we know P(GmM has Qb) —> 0. This gives us our result for
Model B if A! _>_ In log n}.

For smaller M, corresponding to the range 135-3 S p S 25?, more work is required.
First let M = {pN} . Now we will show that there exists an M’, with M—(n log3 n)% S
M’ S M such that

P(GmM’ has Q5) S 3n5p4e‘1'5“. (2.37)

Suppose that no such M’ exists. Then using equation (2.19) we have

P(GM, has Q5) 2 P(GmM' has Qb)P(|E',,,p| = M’) (2.38)

MI

2M:

M 5 4 —1.5d N i N—i
Z 2: (3nPe )(2)P(1—Pl - (2-39)
I=M- ’

M

Then using inequalities (2.35) and (2.39) we see

nsple'l's" Z P(Gnm has Qb) (2.40)
M N . .

Z Z (3n5p4e-1.5d)( )pt(1_ p)N—t. (241)

i=M—M’ 2
So we have

1 M N i N—:‘

-3-_>_ Z 2 p(l-p) - (2.42)
i=M—M'

It follows from the normal approximation to the binomial distribution that the
1' ight hand side of inequality (2.42) approaches % as n —-> 00, so we have a contradic-

tion. Hence there exists an M’, with M — (nlog3 n)i S M’ S M such that

P(GmM. has Q.) g 3n5p46-1'5". (2.43)

22

Now let
P1 = P(GmMI has Q5 and Gn,M has Q5)
and
P2 = P(GmM’ does not have Q1, and Gn,M has Q5).
Clearly

P(GmM has Q.) = P1 + P). (2.44)

Next we show that both P1 —-+ 0 and P2 —) 0 as n —> 00.

First we see

P1 : P(Gn,hf’ has Q5 and Gn,M has Q5)
_<_ P(Gn,MI has Q5)

S 3125p4e‘1°5“ —) 0.

Now we focus on P2. Let n be the probability that GmM: does not have Q), but
Gn,M obtained from GmM’ by adding M — M’ edges has at least one of its new edges
incident with a small vertex or a neighbor of a small vertex. Clearly P2 S 1r. To show
that P2 —2 0, we will show that 1 — 71' ——> 1. Now 1 —- 7r is the probability that GmM:
does not have Q5 and GmM obtained from GmM: by adding M — M’ edges has none of
its new edges incident with a small vertex or a neighbor of a small vertex. The number
of positions where these new edges may be placed is at least N — M’ — n§(1 + %).
To see this, observe that the number of small vertices and their neighbors is at most
ni' + nif—o. There could be at most n — 1 edges incident with each of these. And so

n(ni' + "iiiol is an upper bound on the number of possible edges that are incident

23

with a small vertex or a neighbor of a small vertex. Thus

(N—M’—n§(1+2%))
(1 — 7r) 2 $3221; ) . (2.45)

M—M’

The right side of (2.45) is of the form
Q. (2.46)

The behavior of such an expression was considered in [Pa85]. It is shown that if

a—b

 

 

k2 b2 —+ 0 (2.47)
and
k b — a 2 —+ 0 (2 48)
b — k '
then

). (2.49)

 

Now since M —M’ S (n log3 n)i and n§(1+ 5%) = 0(ni log n), we see that conditions
(2.47) and (2.48) hold and that the binomial expression in (2.45) is asymptotic to 1.
Therefore 7r —+ 0 and then so must P2. This shows that both P1 —> O and P2 —+ 0

and it follows from equation (2.44) that
P(GmM has Qb) -—> 0.

Hence property Q1, almost surely does not hold for Model B when M = pN _>_
I§nlog it]. That is, almost surely the distance between any two small vertices is at

least ﬁve. I.

Chapter 3

Edge-Dis joint Trees

3.1 The Theorem of Nash-Williams

We will make use of a beautiful theorem found independently by N ash-Williams
and Tutte, which provides necessary and sufﬁcient conditions for a graph to have
k edge-disjoint spanning trees. We use P to denote a partition of the vertex set
of a graph and IPI is the number of parts in P. For a graph G with partition P,
contracting each part of P to a single vertex leaves the graph which we denote as
Gp. We will call the edges of Gp external edges and denote them by either E (Gp) or
Ep(G).

Theorem 3.1.1 ([N-W61] , [Tu6l]) A graph G has I: edge—disjoint spanning trees
if and only if
IEr(G)I Z I~‘(I7’I - 1) (3-1)

for every partition P of V(G).
The necessity is easy to show. Let G be a graph with k edge-disjoint spanning

trees T1, T2, . . .T), and let P be a partition of V(G). Then each (T;)p is connected

and so it has at least IPI — l edges. Hence
IEMG I > Z IBMT I > k( (IPI - 1) (3-2)

24

25

as required.

The proof of the sufﬁciency is more complicated. We will provide an algorithmic
proof for the case when I: = 2 that is implicit in [N-W61]. The algorithm will explicitly
ﬁnd two edge-disjoint spanning trees in any graph that satisﬁes condition (3.1). We
will prove results for arbitrary 11: when it is no more complicated than the case in

which I: = 2.

We need the following deﬁnitions. In a graph G for any non-empty subset X of
V(G) let Aa(X) = lc(|XI — 1) — IE(X‘)I. The set X is called .critical if Aa(X) = 0.
A partition P of V(G) is admissible if it satisﬁes inequality (3.1) and critical if the
inequality can be replaced with an equality. A graph G is called admissible if all
partitions of V(G) are admissible and critical if IE(G)I = lc(IV(G)I — 1)

The algorithm is recursive. We wish to reduce a graph to one of the base cases

when IV(G)I = 1,2 or 3.

Start the algorithm by considering a graph G. Every partition of V(G) must
be examined to make sure G is admissible and to ﬁnd which partitions are critical.
Checking every partition will mean that this algorithm cannot be done in polynomial
time. Every graph returned by the algorithm will be admissible. If G = K1, then
we will consider G to be admissible and to have two edge-disjoint spanning trees.
If G has two or three vertices and is admissible, it will be clear that there are two

edge-disjoint spanning trees and they will be easily found.

For IV(G)I 2 4, every graph G falls into one of three classes:

(I) The only critical partition is P = {V(G)}, the trivial partition (which is always
critical).

(II) There is a critical partition that is neither the trivial partition, P : {V(G)},

nor the singleton partition, P = V(G).

26
(III) The singleton partition and the trivial partition are the only critical parti-
tions.

For each of the three classes the algorithm will send a graph or a set of graphs
that have fewer edges and / or fewer vertices than the original graph back to the start

for treatment.
Class I graphs:
In this case, for every partition P # {V(G)}

lEr(G)| > k(l7’| - 1)-

So we may pick any 6 E E(G) and remove it, creating an new graph H = G — {e}.

Now every partition P of V(H) has
IEPIHII Z HIPI - 1)
and thus H is admissible and may be returned to the beginning of the algorithm.

Class II graphs:

Here there is a critical partition P of V(G) other than the singleton or trivial
partition, so
IEr(G)I = HIPI - 1)
with IPI 515 l and IPI 79 IV(G)|. Let P = {X1,X2,...,X¢}. For any X16 P, let Q be
a partition of X; and ’R = (P — {X;}) U Q. Then since G is admissible,

HIRI - 1) S IE‘R(G)I = IEr(G)I + IEQ(X£")| (3-3)

and so
IEQ(X.")I Z HIRI -1) - lEr(G)| = (3-4)
MRI-1) - kIIPI - 1) = (3-5)

MRI - IPI) = k(|Q|-1)- (3-6)

27
Thus we see that X: is admissible since Q is arbitrary and that every X: is admissible
since i is arbitrary.

Now consider the graph Gp. Any partition 8 of V(G'p) is also a partition of
V(G). Since G is admissible, Gp is also admissible. We can then return IPI + 1
graphs, Xf, X5", . . . ,X,‘ and Gp, to the beginning of the algorithm. In each of these
graphs, 2 edge-disjoint spanning trees will be constructed and then put together to

form 2 edge-disjoint spanning trees on G.
Class III graphs:
We need the following lemmas.

Lemma 3.1.2 ([N-W61]) Let G be a critical graph. Then G is admissible if and
only ifAG(X) Z 0 for every 0 # X C V(G).

Proof: Let us start by showing the necessity. If G is admissible, let X C V(G) and
the complement of X be X = {1:1, ‘02, . . . , vr}. Also let P = (X, {v1}, {v2}, . . . , {v,}}.

Then
mM)=mmawwwm on
=HMW-FWWHWM4hmn (w)
=kmm4wmumﬂnml as

= Ik(IV(G)I - 1) - IE(G)” + [132(0) - k(l7’| - 1)] (3-10)
2 o (3.11)

using that G is critical and admissible. Now let us show the sufﬁciency. We assume

A0(X) 2 0 for all X C V(G). For any partition P of V(G),

IEr(G)I = IE(G)|- Z IE(X1)I (3-12)

XiE‘P

zkwmvu-ZMM—mwwvn (we

XiGP

 

28

so G is admissible. This ends the proof of the lemma.

We also need some results about critical graphs with IV(G)| 2 4 and k = 2 that

are summarized in the following lemma.

Lemma 3.1.3 Suppose a graph G is critical with IV(G)I Z 4 and Aa(X) Z 0 for
every 0 yé X C V(G). For k = 2 the following hold:

(a) There are no vertices of degree two.
(b) There exists a vertex of degree three.
(c) For any vertex v of degree three, IN(v)| > 1.

(d) If a vertex v has degree three and X is a critical set not containing v, then

IN(v)ﬂXI Sl

Proof: (a) If v is a vertex of degree 2, then the partition {{v}, V(G) — {v}} is
critical. But we are assuming that G has only the singleton and trivial partitions as

critical partitions.

(b) The average degree of the vertices in G is

2|E(G)| : 2(2(|V(G)|—1))= 4 __ 4 < 4
|V(G)| |V(G)l (V(G): '

 

 

Since there are no vertices of degree 2, then a vertex of degree 3 must exist.

(c) If v has degree three and N(v) : {u}, a single vertex then
Ac;({v,u}) = 2(2 — 1) — 3 = —1

which contradicts Lemma 3.1.2.

((1) First suppose the vertex v has degree three and that N (v) C X. Then since
Aa(X) = 0, we see that Ag(X U {v}) = 0 which contradicts Lemma 3.1.2. So one of

v’s neighbors is not contained in X.

29

Next suppose X contains two neighbors of v. Let X = {u1, U2, . . . , u,} and con-

sider the partition

’p = {X U {1)},{u1},.. .,{Ur}}-

Using that G is a critical graph, X is a critical set IPI = IXI + 1, we see

IE2(G)| = IE(G)|-IE(1’{"‘)|-2 (314)
= 2(|X|+|X|+1—1)—2(|X|—1)—2 (3.15)
= 2(|7‘(’|+1—1) (3.16)
= 2(|r|—1) (3.17)

But this contradicts the assumption that G only has the singleton and trivial parti-

tions as critical partitions. This ends the proof of the second lemma.

Let v be a vertex with degree three and with neighbors u and w. Let H be the
graph constructed from G by adding an edge e between u and w while deleting v and
the edges incident to v. Clearly H is critical and we must show that H is admissible.

For any set X C V(H), if u or w are not in X, then

AH(X) = A(AX) 2 0-

If both u and w are in X, then because X cannot be critical and contain both u and
w we know AC;(X) > 0. From this we see that AH(X) = Ag(X) - 1 Z 0. Thus by
Lemma 3.1.2 we know that H is admissible. We then may return H to the beginning

of the algorithm.

From H we construct two edge—disjoint spanning trees in G as follows: When H
returns it will have two edge-disjoint spanning trees and the edge e = {u, w} will be
in one of them. For that tree, replace c with the edges {v,u} and {v,w}, and add

the third edge incident to v to the other tree.

30

Thus by reducing the graph G to one of the base cases we may construct two edge

disjoint trees on G. I

The computational complexity of this algorithm is, of course, exponential because
every partition of the vertex set must be examined. On the other hand, the proof
seems easier to follow and more convincing than traditional proofs when presented
in this style. Furthermore it is apparent that the traditional proofs do not lend
themselves easily to adaptation for efﬁcient algorithms. Dave Johnson has told us
that ﬁnding edge-disjoint spanning trees can actually be achieved in polynomial time
(email communication). The best known treatment makes use of the matroid greedy

algorithm. See [RoT85] for related references.

3.2 Edge Boundary Lemma

To implement the theorem of Nash-Williams, we must have some knowledge of the
edge boundary of a set of vertices. We need to show that a vertex set of small order
will have a large number of edges joining it to the rest of the graph. For a subset S

of V(G), let us deﬁne the edge boundary ofS to be

61(5) = {(155} | u e s, v e V(G)\S}. (3.18)

Lemma 3.2.1 (Edge Boundary Lemma) Let the edge probability p be deﬁned by
equation (2.5) so that almost all graphs have minimum degree 11: and let 0 < e < 1 be
ﬁxed. Then almost every graph G has the following property: For every subset S of
V(G) with IS'I S en we have

I61(5)I Z k|S|. (3-19)

31

Proof: The expected number of sets with cardinalities between the integers a and
b inclusive for which condition (3.19) does not hold is
b ks—l _ ' .
F(a.b) = Z: (") Z (3”,. 3))17'0 — P)’(n_”_’- (3.20)
a=a j=1
We would like to ﬁnd the largest interval possible on which F (a, b) -+ 0 as n —> 00.
Now by using the fact that the inner sum is a binomial tail and applying Stirling’s

formula we see

 

 

 

 

 

b ”-3 s—1)sn—s sl p{S(n— S)—(l€3—1)+l}

F(“”)- aim i)s—1l”k(1 ( )H [p{s(n: s)+1}—(ks—1)
(3.21)

b
S 3230(1)(:) (S( k: : 111)): ks— 1(1 _ p)s(n-s)—ks-l (3.22)
” 1 — p ne ‘ 3(n - 3)€ “-1 s(n-—s)—ks
‘- 20“)? (I) (W) (1‘ 1”) (3'23)
< 2:: 0(1)1-:){S—)s (((Z _—3—1—)):) (np)" epr—p(n — s — k)]] (3.24)
(l _(1 e’PePk 8
O(-l-0—g) )o(1):[ (ogn) )kn(logn)"‘1ewnI (3.25)
b logn lc- .9 ea: s/ne —w 3

S ;0( logn) )[o (1) {12(logn) "} "I . (3.26)

We now split the sum in (3.26) into two parts. First we would like to have
6012-52 < 1 and {n(logn)""1e“’"}’/" < L where co and L are constants. For this we
need

a = cologn < s

and

s< Cln —ﬂ—b
"' log+(k—1)loglogn+w,, _ p _

 

where c1 = log L. It then follows that F (colog n, 9:) —+ O.

32

Secondly, for the upper part of the sum, if a = 5; and b = an we see

 

Cl (n 1 log k—l w a/n —w 8
_ < _ n n .
F( , en) Fig/p 0(log ) [0(1) 3 {n(log n) e } e (3 27)

 

en 1+‘(k“1l s
z 0( 1 ) [o(l)(log:zzl_c {logn + (k — 1) log log n + ewn}e-Wn(1-C)]
1
(3.28)

—>0

l—c

because the term n in the denominator will dominate. So F(colog 11, en) —* 0 as

n—+oo.

Showing F (0,colog n) --+ 0 cannot be accomplished using the estimates we have
employed here. In fact, we can easily see that the right hand side of (3.26) does not
go to zero if a = l and b = 2. An entirely different approach must be used for sets of
smaller order. First consider sets 8' with ISI S m log 72.. If 3 contains only small
vertices then a consequence of the structural properties of Theorem 2.4.1 is that none
of the vertices in S are adjacent to one another. Hence all of the edges incident with
vertices in S are in 61(5), and since the minimum degree is k, inequality (3.19) holds.
If S contains a large vertex, v, then at least %logn - 20(—Ii+T5 logn = mtg—ﬁlogn

edges incident with v are in 61(5), and again inequality (3.19) is satisﬁed. I

3.3 Threshold Theorem

Now we apply the structural properties, the edge boundary lemma and the theorem
of Nash—Williams to establish our main results. First we will ﬁnd the threshold func-
tion for edge—disjoint spanning trees and as a consequence we also have the threshold

function for collapsibility.

33

Theorem 3.3.1 Let the edge probability be deﬁned by

 

p— logn+(k——1)loglogn+wn
n

where can -—) 00 and can = o(log log n) so that almost all graphs have minimum degree

1:. Then almost all graphs have I: edge-disjoint spanning trees.

Proof: We wish to show that for every partition P of V(G) we have
IENGH Z k(|P| — 1)-
We will use the convention that the t = IPI sets of P are ordered as follows
MI 2. MI 2 .>_ MI-

There are three cases. In the ﬁrst two, 6 is arbitrary.
Case I: IPI S %n +1 and IVII < en.

Since en 2 IVII Z |V2| Z .. . Z IVA, Lemma 3.2.1 will apply to every V5. Hence

1 IPI
IEp(G)| = 536.04): (3.29)
1 IPI
2 52km (3.30)
i=1
nlc
2 72— (3.31)
2 tum—1). (3.32)

Case 2: IPI > %n +1 and “GI < en.

It is sufﬁcient to show that the average number of edges in the edge boundary of

the sets of P is at least 2k almost surely, i. 6.

WI
2 I61(V.-)I 2 2km. (333)

i=1

34

Then it will follow that
IEp(G)| 2 klpl- (334)

We call a set V; of P primary if it consists entirely of large vertices. Otherwise
a set of P is secondary. If a primary set consists of one or two vertices, its edge
boundary has at least 5355'! or 2132561I — 1 edges respectively. In each case, the edge
boundary will have at least 311: edges for n sufﬁciently large. Lemma 3.2.1 implies
that any set with at least three vertices has at least 3k edges in its edge boundary.
Hence all primary sets have at least 3k edges in their edge boundaries. Lemma 3.2.1

also implies that each secondary set has at least k edges in its edge boundary.

Theorem 2.4.1 states that there are at most 121/3 small vertices, so it follows that P
has at most 711/3 secondary sets and at least in — n1/3 primary sets. Thus the number
of primary sets exceeds the number of secondary sets and so the average number of

edges in the edge boundaries of the sets of P is at least 21:.
Case 3: WI] > en.

Let c > % so we have |V,-| < en for i = 2 to t. Let R = U§=2 V.- and then clearly
[RI < m and 61(V1) = 61(R). It follows from Lemma 3.2.1 that for i = 2 to t almost

surely

I510?)

 

2 WI (3.35)

and

|61(V1)| = |61(R)| _>_ klRl- (3-36)

So from these relations

i=2

IPI
we): = -;-(l61(%)|+2|61(14)l) (337)

IV

1
503(3) + k|R|) = HR! (3.33)

IV

k(|P| — 1). (3.39)

35

Thus Theorem 3.1.1 can be applied to all three cases and so we know that a

random graph of minimum degree I: has In edge-disjoint spanning trees a. s. I

It follows from Theorem 3.3.1 that a random graph with minimum degree two
has two edge-disjoint spanning trees almost surely. Hence Theorem 1.1.2 implies
that with probability approaching 1 these are collapsible. Obviously a graph with a
vertex of degree one is not collapsible. Thus, we have determined the threshold for

collapsibility.

Corollary 3.3.2 Let the edge probability p be deﬁned by equation (2.5) with k = 2
so that almost all graphs have minimum degree two. Then almost all graphs are

collapsible.

Theorem 3.3.1 and Corollary 3.3.2 can be refined. Suppose p is deﬁned by equation
(2.5) but can —> c, for a constant c. No doubt it can be shown that the probability that
the minimum degree is k and the probability that there are k edge-disjoint spanning
trees are the same in the limit, namely exp[—{exp(—c)}/(lc — 1)!], (see [B085], p. 61

for further details on the degree distribution).

Our proof of Theorem 3.3.1 is not algorithmic. On the other hand, if the minimum
degree is at least k = 2r + 1, then there is a method for finding 1' + 1 edge-disjoint
spanning trees in a random graph. First we need another consequence of the Edge

Boundary Lemma 3.2. 1.

Theorem 3.3.3 Let the edge probabilityp be deﬁned by equation (2. 5) with k 2 2r+1.
Then a random graph G has r edge-disjoint spanning cycles, C1, C2, . . . , Cr, and the
subgraph H, which is obtained from G by deleting the edges of the r spanning cycles,

is connected.

 

36

Proof: Bollobas and Frieze have shown in [BoF 85] that a random graph G with
minimum degree 21‘ + 1 has r edge-disjoint spanning cycles. Now ﬁx 6 > 1/2. Then
from Lemma 3.2.1 it follows that for any subset S of V(G), with |S| S n/2, we have

as

I61(S)| 2 (2r +1)|S|. (3.40)

Removing the edges of r edge-disjoint spanning cycles from G means at most 2r|5 I

edges are removed from 61(5). Thus
|51(5)| - 21‘ISI 2 ISI > 0, (3.41)

so 61(5) in H is non-empty. Hence H is almost surely connected. I

Suppose we have a random graph G with minimum degree at least 2r + 1. The
algorithm of [BoF F87] can be used to ﬁnd r edge-disjoint spanning cycles, and hence
r edge-disjoint spanning paths. Let H be the graph obtained by deleting the edges of
these paths from G. Theorem 3.3.3 implies that H is almost surely connected and so
Depth-First Search on H will produce another spanning tree of G disjoint from the r

paths.

All of the results in this section can be converted to Model B. Let us restate

Corollary 3.3.2.

Corollary 3.3.4 Let the number A! of edges be given by
M = [lg-(logn + log logn + wn)J , (3.42)

where can —i 00 but can = o(log log n). Then almost all graphs in 9(n, M) are collapsi-

ble.

We conclude by pointing out that Frieze and Luczak [FrL90] established a theorem

corresponding to Theorem 3.3.1 for a slight variation of Model C. To obtain the

37

graphs of their version, the orientation of the r arcs out of each vertex is ignored but
a symmetric pair of arcs becomes a pair of multiple edges. They showed that these
graphs obtained from r-out almost surely have r edge-disjoint spanning trees. They
used the N ash-Williams theorem but their proof was signiﬁcantly different because of

the nature of the probability model.

3.4 Regular Graphs

In a regular graph all vertices have the same degree. A graph is r-regular if
each vertex has degree r. Our sample space for random regular graphs consists of
all labeled r-regular graphs on n vertices. We use the equiprobable model. In this

section we will explore the collapsibility of regular graphs.

The connectivity n(G)of a graph G is the minimum number of vertices whose
removal from G results in a disconnected or trivial graph. The edge connectivity /\(G)
of a graph G is the minimum number of edges whose removal from G results in a
disconnected or trivial graph. We will now determine the number of edge-disjoint

spanning trees in a random regular graph.

Theorem 3.4.1 For a ﬁxed r 2 3 almost all r-regular graphs have ng edge-disjoint

spanning trees.

Proof: Wormald has shown that for r 2 3, almost all r-regular graphs have

connectivity 1' (see [W081]). Now let G be an r-regular graph, 1' Z 4, and let
P={V1.V2,---,V1}

be a partition of V(G). Using the fact that E(G) 2 A(G) and the above mentioned

result of Wormald, we see that I61(V.-)| Z r for all 0 S i S t almost surely. Therefore

38

for almost all r-regular graphs,

1 IPI

133(0)) = 5};|61(V.-)| (3.43)
1 IPI

2 §£=lr (3.44)

2 [glam—1). (3.45)

It then follows from Theorem 3.1.1 that almost all r-regular graphs will have (gj

edge-disjoint spanning trees. I

Using Theorem 1.1.2, we can easily arrive at the following corollary.
Corollary 3.4.2 For ﬁxed r 2 4, almost all r-regular graphs are collapsible.

The question as to whether random 3-regular graphs (also called cubic graphs) are
collapsible has yet to be answered. It is a much more difﬁcult problem. As stated
above, it is not even known if the Augmented Petersen graph is collapsible. The use
of “deﬁnition two” of collapsibility will lead to a rather concise equivalent statement
of the problem. Recall that a graph G is collapsible if for every subset S of V(G) with
even cardinality, there is a subgraph P such that G — E (F) is connected and v E S if
and only if the degree of v in I‘ is odd. So if G is a cubic graph, in order for G - E (F)
to be connected the only odd degree allowed in F is one. This means I‘ must be a
collection of paths. Thus a cubic graph G is collapsible if and only if for every subset
S of V(G) with even cardinality there exist IS I /2 disjoint paths whose ends are the

vertices of S and the removal of the edges of these paths does not disconnect G.

Let us reﬁne the problem further. Suppose G is a cubic graph. Consider “deﬁnition
one” of collapsibility and let the subset S of V(G) be the empty set. We wish to ﬁnd

a spanning connected subgraph H in which the vertices of 3 have odd degree. Since

39

G is 3—regular, all vertices of H must have degree two. Hence, this case shows that if a
cubic graph G does not have a spanning cycle, it is not collapsible. It has been shown
by Robinson and Wormald that almost all cubic graphs have a spanning cycle (see
[ROW92]), so it is possible that almost all cubic graphs are collapsible. However there
are examples of cubic graphs that contain a spanning cycle and are not collapsible.
A diamond is a K4 with one edge removed. By arranging m diamonds in a circle and
connecting each one to its successor by a new edge joining vertices of degree two, we
create a ring of m diamonds. This ring is clearly hamiltonian but not collapsible if

m 2 4, because on contracting the triangles in the diamonds, a cycle Cm is left.

3.5 Large Eulerian Subgraphs

Let p(G) be the minimum number of edges whose removal from a graph G leaves
a spanning eulerian subgraph H. It follows from a result in [Pa88] that if pn _>_ logn
and p —+ 0 as n —> 00, then the number of vertices with odd degree is asymptotic to
n/2. Furthermore if pn 2 210g 12, then the subgraph induced by the vertices of odd
degree has a perfect matching (a. 8.). Hence for pn 2 210g n, p aproaches n /4. Our

object now is to estimate bounds on ,u for smaller p.

Suppose p is deﬁned by equation (2.5) with k 2 3 so that the minimum degree
is at least 3 (a. s.). From Theorem 3.3.3 we know that a random graph G has a
spanning cycle C whose edges may be removed and a connected graph will remain.
This cycle can be expressed as the edge-disjoint union of paths joining vertices of odd
degree. On removing the edges of alternate paths of the cycle from G, we obtain
an eulerian subgraph. Clearly no more than n / 2 edges need to be removed. Hence

u S n/ 2 almost surely.

On the other hand, suppose p is deﬁned by equation (2.5) with k = 2 so that

40

a. s. the minimum degree is 2. We know from Theorem 3.3.1 that a random graph
G will have two edge-disjoint spanning trees, T1 and T2. Now arrange the vertices
of odd degree in pairs arbitrarily and consider the paths in T1 that join each pair.
By forming the symmetric difference of these paths, we obtain a set of edge-disjoint
paths in T1. The deletion of the edges in these paths leaves an eulerian graph and

hence u S n —1 (a. 3.).

These results are summarized in the following theorem.

Theorem 3.5.1. Suppose the edge probability p of a random graph is deﬁned by

equation (2.5) and e > 0 is arbitrary.

Iflc 2 3, then a. s.

(1 — e)n/4 S p S n/2,

and iflc = 2, then a. s.

(1—e)n/4SuSn—1.

N ow there is the problem of reﬁning these results. In the range where pn = clog n,
1 < c < 2, can the upper bound of n / 2 be lowered? For p deﬁned as in equation (2.5),
a random graph will most likely not have a matching on the vertices of odd degree, so
how may the lower bound of (1 — e)n / 4 be raised? And ﬁnally, for the case 11: = 2 in
Theorem 3.5.1, how much can the upper bound be improved? If a spanning cycle on
the vertices of degree at least three can be found whose removal almost surely does

not disconnect the graph, the upper bound can be lowed to n / 2.

Bibliography

[B079] B. Bollobés, Graph Theory, An Introductory Course, Springer-Verlag,
New York, (1979).

[B085] B. Bollobas, Random Graphs, Academic, London, (1985).

[BOF85] B. Bollobés and A. M. Frieze, On matchings and hamiltonian cycles in
random graphs, Annals of Discrete Math. 28 (1985) 23-46.

[BoFF87] B. Bollobas, T.I. Fenner and A.M. Frieze, An algorithm for ﬁnding hamil-
ton paths and cycles in random graphs, Combinatorica 7 (1987) 327-341.

[BoT86] B. Bollobas and A. Thomason, Threshold functions, Combinatorica 7
(1986) 35-38.

[Ca88a] P. A. Catlin, A reduction method to ﬁnd eulerian subgraphs, J. Graph
Theory 12 (1988) 29-45.

[Ca88b] P. A. Catlin, Supereulerian graphs, collapsible graphs, and four-cycles,
Congr. Numer. 58 (1988) 233-246.

[ErR59] P. Erodbs and A. Rényi, On random graphs 1, Publ. Math. Debrecen 6
(1959) 290-297.

[ErR60] P. Erodés and A. Rényi, On the evolution of random graphs, Magyar Tud.
Akad. Mat. Kutato’ K521. 5 (1960) 17-61.

[ErR61] P. Erodbs and A. Rényi, On the strength of connectedness of random
graphs, Acta Math. Acad. Sci. Hungar. 12 (1961) 261-267.

[FrL90] A. M. Frieze and T. Luczak, Edge disjoint spanning trees in random
graphs, Periodica Mathematica Hungarica 21 (1990) 35-37.

[Ja85] F. Jaeger, A survey of the cycle double cover conjecture, Annals of Dis-
crete Math. 27 (1985) 1-12.

[N-W6l] C. St.J. A. Nash-Williams, Edge-disjoint spanning trees of ﬁnite graphs,
J. London Math. Soc. 36 (1961) 445-450.

[Pa85] E. M. Palmer, Graphical Evolution, Wiley, New York (1985).

[Pa88] E. M. Palmer, Eulerian subgraphs of random graphs, Congr. Numer. 63
(1988) 139-145.

41

42

[RoW92] R. W. Robinson and N. C. Wormald, Almost all cubic graphs are hamil-
tonian, Random Structures and Algorithms 2 (1992) 117-125.

[ROT85] J. Roskind and R. E. Tarjan, A note on ﬁnding minimum-cost edge-
disjoint spanning trees, Math. Oper. Res. 10 (1985) 701-708

[8273] G. Szekeres, Polyhedral decomposition of cubic graphs, Bull. Austral.
Math. Soc. 8 (1973) 367-387.

[Tu6l] W. T. Tutte, On the problem of decomposing a graph into n factors, J.
London Math. Soc. 36 (1961) 221-230.

[W081] N. C. Wormald, The asymptotic connectivity of labelled regular graphs,
J. Combinatorial Theory, Ser. B 31 (1981) 156-167.

   

MICHIGAN STATE UNIV. LIBRARIES
[Illlllllllll[WWlllllllllllllml[Illllllll
31293008853253