Omer Giménez
email: omer.gimenez@gmail.com

Dieter Mitsche
email: dmitsche@unice.fr

Marc Noy
email: marc.noy@upc.edu

Maximum degree in minor-closed classes of graphs

Given a class of graphs G closed under taking minors, we study the maximum degree ∆n of random graphs from G with n vertices. We prove several lower and upper bounds that hold with high probability. Among other results, we find classes of graphs providing orders of magnitude for ∆n not observed before, such us log n/ log log log n and log n/ log log log log n.

Introduction

A class of labelled graphs G is minor-closed if whenever a graph G is in G and H is a minor of G, then H is also in G. A basic example is the class of planar graphs or, more generally, the class of graphs embeddable in a fixed surface.

All graphs in this paper are labelled. Let G n be the graphs in G with n vertices. By a random graph from G of size n we mean a graph drawn with uniform probability from G n . We say that an event A in the class G holds with high probability (w.h.p.) if the probability that A holds in G n tends to 1 as n → ∞. Let ∆ n be the random variable equal to the maximum vertex degree in random graphs from G n . We are interested in events of the form ∆ n ≤ f (n) w.h.p. and of the form ∆ n ≥ f (n) w.h.p.

Typically f (n) will be of the form c log n for some constant c, or some related functions. We say that f (n) = O(g(n)) if there exists an integer n 0 and a constant c > 0 such that |f (n

)| ≤ c|g(n)| for all n ≥ n 0 , f (n) = Ω(g(n)), if g(n) = O(f (n)), and finally f (n) = Θ(g(n)), if both f (n) = O(g(n)) and f (n) = Ω(g(n)) hold. Also, f (n) = ω(g(n)), if lim n→∞ |f (n)|/|g(n)| = ∞, and f (n) = o(g(n)), if g(n) = ω(f (n)).
Throughout this paper log n refers to the natural logarithm.

A classical result says that for labelled trees ∆ n is of order log n/ log log n (see [START_REF] Moon | On the maximum degree in a random tree[END_REF]). In fact, much more precise results are known in this case, in particular that (see [START_REF] Carr | The maximum degree in a random tree and related problems[END_REF]) ∆ n log n/ log log n → 1 in probability.

Many more results about the distribution of maximum degree, its concentration, and several different models of randomly generated trees can be found in the survey of [START_REF] Janson | Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation[END_REF].

McDiarmid and Reed [START_REF] Mcdiarmid | On the maximum degree of a random planar graph[END_REF] show that for the class of planar graphs there exist constants 0 < c 1 < c 2 such that c 1 log n < ∆ n < c 2 log n w.h.p.

More recently this result has been strengthened using subtle analytic and probabilistic methods [START_REF] Drmota | The maximum degree of planar graphs[END_REF], by showing the existence of a computable constant c such that ∆ n log n → c in probability.

For planar maps (planar graphs with a given embedding), more precise results on the distribution of ∆ n can be found in [START_REF] Gao | The distribution of the maximum vertex degree in random planar maps[END_REF].

Analogous results have been proved for series-parallel and outerplanar graphs [START_REF] Drmota | The maximum degree of series-parallel graphs[END_REF], with suitable constants. Using the framework of Boltzmann samplers, results about the degree distribution of subcritical graph classes such as outerplanar graphs, series-parallel graphs, cactus graphs and clique graphs can also be found in [START_REF] Bernasconi | The Degree Sequence of Random Graphs from Subcritical Classes[END_REF]. This paper also contains conjectures of the exact values of c OP (c SP , respectively) so that the maximum degree in outerplanar graphs (series-parallel graphs, respectively) will be roughly c OP log n (c SP log n, respectively).

The goal in this paper is to analyze the maximum degree in additional minor-closed classes of graphs. Our main inspiration comes from the work of McDiarmid and Reed mentioned above. The authors develop proof techniques based on double counting that assume only mild conditions on the classes of graphs involved. We now explain the basic principle.

Let G be a class of graphs and suppose we want to show that a property P holds in G w.h.p. Let B n the graphs in G n that do not satisfy P (the 'bad' graphs). Suppose that for a constant fraction α > 0 of graphs in B n we have a rule producing at least C(n) graphs in G n (the 'construction' function). A graph in G n can be produced more than once, but assume every graph in G n is produced at most R(n) times (the 'repetition' function). By double counting we have

α|B n |C(n) ≤ |G n |R(n), hence α |B n | |G n | ≤ R(n) C(n) .
If the procedure is such that C(n) grows faster than R(n), that is R(n) = o(C(n)), then we conclude that

|B n | = o(|G n |)
, that is, the proportion of bad graphs goes to 0. Equivalently, property P holds w.h.p. We often use the equivalent formulation C(n)/R(n) → ∞.

We will apply this principle in order to obtain lower and upper bounds on the maximum degree for several classes. In this context, lower bounds are easier to obtain, and only in some cases we are able to prove matching upper bounds. The proof of the upper bound for planar graphs in [START_REF] Mcdiarmid | On the maximum degree of a random planar graph[END_REF] depends very strongly on planarity, and it seems difficult to adapt it to general situations; however we obtain such a proof for outerplanar graphs. On the other hand, we develop new tools for proving upper bounds based on the decomposition of a connected graph into 2-connected components.

Here is a summary of our main results. We denote by Ex(H) the class of graphs not containing H as a minor. All the claims hold w.h.p. in the corresponding class, and c, c 1 and c 2 are suitable positive constants. The fan graph F n consists of a path with n -1 vertices plus a vertex adjacent to all the vertices in the path.

• In Ex(C 4 ) we have, for all > 0, (2 -) log n log log n ≤ ∆ n ≤ (2 + ) log n log log n .

• In Ex(C 5 ) we have, for all > 0, (1 -) log n log log log n ≤ ∆ n ≤ (1 + ) log n log log log n .

• In Ex(C 6 ) we have c 1 log n log log log n ≤ ∆ n ≤ c 2 log n log log log n .

• In Ex(C 7 ) we have c 1 log n log log log log n ≤ ∆ n ≤ c 2 log n log log log log n .

• If H is 2-connected and contains C 2 +1 as a minor, then in Ex(H) we have

∆ n ≥ c log n log ( +1) n ,
where log ( +1) n = log • • • log n, iterated + 1 times.

• If H is 2-connected and is not a minor of F n for any n, then in Ex(H) we have

∆ n ≥ c log n.
The results on Ex(H) also hold when forbidding more than one graph as a minor, as discussed in the next section.

Organization of the paper. In Section 2 we prove the lower bounds for the maximum degree. In Section 3 we determine the structure of 2-connected graphs in the classes Ex(C 5 ), Ex(C 6 ) and Ex(C 7 ). This is quite technical and based on case analysis. The reason we undertake this analysis is to exemplify our technique for proving upper bounds and to show that different asymptotic estimates for the maximum degree are indeed possible. The proofs for the upper bound are contained in Section 4. We conclude with some remarks and several conjectures and open problems.

Lower bounds

A pendant vertex is a vertex of degree one. The following lemma follows from [START_REF] Mcdiarmid | Random graphs from a minor-closed class[END_REF]. Lemma 1. Let H 1 , . . . , H k be 2-connected graphs and let G = Ex(H 1 , . . . , H k ). Then there is a constant α > 0 such that a graph in G n contains at least αn pendant vertices w.h.p.

To illustrate our proof technique, we reprove the following well-known result (see [START_REF] Moon | On the maximum degree in a random tree[END_REF], and see [START_REF] Carr | The maximum degree in a random tree and related problems[END_REF] for more precise results, as mentioned above), but without the need of enumerative tools. Lemma 2. Let > 0 be any constant. In the class of forests, w.h.p.

(1 -) log n log log n ≤ ∆ n .
Proof. Let G be the class of forests, and G n the class of forests with exactly n vertices. Let > 0 be any constant and let B n ⊆ G n denote the set of bad graphs with ∆ n < (1 -) log n log log n , and suppose for contradiction that |B n | ≥ µ|G n | for some µ > 0, infinitely often. Our goal is to show that we can obtain

ω(|B n |) new graphs in G n , or equivalently, C(n)/R(n) → ∞, contradicting |B n | ≥ µ|G n |. Consider the subclass B n ⊆ B n of graphs in B n with at least αn pendant vertices. By Lemma 1, |B n | = (1 + o(1))|B n |.
Let G be a graph in B n . Choose from the pendant vertices a subset of size s + 1, where s = (1 -) log n log log n , and delete all their pendant edges. Among those choose a vertex, call it v 1 , and make it adjacent to all other s vertices. Finally, choose a vertex u different from the s + 1 chosen vertices, and make u adjacent to v 1 (we have at least n -s ≥ n/2 choices for u). In this way one can construct at least αn s+1 (s + 1) n 2 graphs. From how many graphs G may the newly constructed graph G come? We identify v 1 as the only vertex with largest degree in G and u as the only non-pendant neighbor of v 1 . In order to reconstruct G completely we only need to reattach the s + 1 vertices in all possible ways, which can be done in at most n s+1 ways. Hence

C(n) R(n) ≥ αn s+1 (s + 1)n 2n s+1 ≥ n(α/2) s+1 2s! .
Taking logarithms, this gives log Now we are ready to state new results that can be obtained using our techniques. In order to prove a lower bound for ∆ n in a class G n , the basic idea is to generalize the previous proof. Take a graph G in G n whose maximum degree is too small (a bad graph), take enough pendant vertices and make with them a special graph S rooted at a special vertex v (in the previous proof a star rooted at its center), and attach S to G through a single edge, producing a new graph G in G n . Then v becomes the unique vertex of maximum degree s = |S|, and G can be reconstructed from G easily by reattaching the vertices in S, which are neighbors of v in G . Double counting is then used to show that the proportion of bad graphs goes to 0 as n goes to infinity. Theorem 3. The following claims refer to the class Ex(H 1 , . . . , H k ).

C(n) R(n) ≥ log n -s log s + O(s) = log n -(1 -)(1 + o( 1
1. Let c be a positive constant satisfying c <

= c log n . Let G be a graph in B n ⊆ B n .
Choose an ordered list v 1 , . . . , v h of h pendant vertices in G, delete the edges joining the v i to the rest of the graph, and make a copy of F h with a path v 2 , . . . , v h and v 1 adjacent to all of them. Select a vertex u of G different from the v i and make it adjacent to v 1 . The graph G constructed in this way belongs to G n , since the H i are 2-connected and none of them is a minor of a fan graph, and has the same number of vertices as G.

The number of graphs constructed in this way is at least (where (m) k denotes a falling factorial)

(αn) h (n -h) ≥ αn 2 h n,
the last inequality being true for n large enough; we use the fact that h = c log n is small compared with n. How many times a graph G can be constructed in this way? Since G ∈ B n , v 1 can be identified as the only vertex of degree h. Vertices v 2 , . . . , v h can be identified as the neighbors of v 1 inducing a path (among the neighbors of v 1 , u is the only cut-vertex, and hence it can be identified easily). In order to recover G, we delete all the edges among the v i and the edge v 1 u, and make v 1 , . . . , v h adjacent to one of the remaining vertices through a single edge. The number of possibilities is at most

(n -h) h ≤ n h . Summarizing, we can take C(n) = (α/2) h n h+1 and R(n) = n h . Then C(n) R(n) ≥ n(α/2) c log n ,
which tends to infinity if c < 1 log(2/α) . This finishes the proof. 2. Assume now that the H i contain C 4 as a minor, that is, they all contain a cycle of length at least four. As before, let G = Ex(H 1 , . . . , H k ), let B n ⊆ G n be the graphs with ∆ n < (2 -) log n/ log log n, and let s = (2 -) log n/ log log n . Let G be a graph in B n . Choose an (unordered) set of s + 1 pendant vertices v 1 , . . . , v s+1 in G, and delete the edges joining the v i to the rest of the graph. Among those choose one of them, say v 1 , and make it adjacent to all others. The other s vertices are paired up, and vertices of pairs are made adjacent (if s is odd, one vertex remains unpaired). Finally, another pendant vertex u is chosen and made adjacent to v 1 . Note that there are at least αn/2 choices for u. There are thus at least αn s+1 (s + 1) ((s -1)!!) (αn/2) constructions, where (2k -

1)!! = 1 • 3 • • • (2k -1)
. The graph G constructed in this way belongs to G n , and has the same number of vertices as G. When reconstructing G, v 1 can be identified as the unique vertex of maximum degree, and u is identified as the only neighbor of v 1 adjacent to a vertex which is not a neighbor of v 1 . Thus, only the s + 1 chosen vertices have to be reattached, and there are at most n s+1 choices. Hence,

C(n) R(n) ≥ αn s+1 ( 1 2 αn) ((s + 1)!!) n s+1 ≥ ( 1 2 α) s+2 ((s + 1)!!) n (s + 1)! .
Using (2g -1)!! = (2g)!/(2 g g!) and taking logarithms we obtain log

C(n) R(n) ≥ log n -(s/2) log s + O(s) = log n -(1 -( /2))(1 + o(1)) log n,
which tends to infinity, as desired.

3. Now we may assume that the H i contain C 5 as a minor. As before, Let G = Ex(H 1 , . . . , H k ) and let B n ⊆ G n be the graphs with ∆ n < (1 -) log n/ log log log n, and let s = (1 -) log n/ log log log n .

Let F n,m be the following graph: take m disjoint copies of K + 2,n-1 (the complete bipartite graph K 2,n-1 plus an edge joining the two vertices in the part of size two), and glue them together by identifying a vertex of degree n -1 in each copy. Notice that the longest cycle in F n,m is C 4 , and that F n,m has mn + 1 vertices. Let G be a graph in B n . For an integer s < s to be made precise below, choose a set of s + 1 pendant vertices v 1 , . . . , v s+1 in G, delete the edges joining the v i to the rest of the graph, and make a copy of F r,s/r with the v i , where r is an integer to be determined later. Let v 1 be the vertex chosen to be adjacent to all other v i (there are s + 1 choices for this vertex). Select a vertex u of G different from the v i and make it adjacent to v 1 . The graph G constructed in this way belongs to G n , since the H i are 2-connected and have no cycle of length more than four, and has the same number of vertices as G.

The number of graphs constructed in this way is at least αn s+1 (s + 1) s r,...,r r s/r n 2 (s/r)! ,

where the first binomial is for the choice of the pendant vertices; (s + 1) is for the choice of the center vertex v 1 , the multinomial coefficient divided by (s/r)! stands for a lower bound on the number of partitions of the s vertices into groups of size r; the factor r s/r for the choice of the vertices of degree r in each group; and finally n/2 is a lower bound for the choices of the target vertex u. The number of ways such a graph G can be constructed is at most n s+1 , the argument is the same as before. Therefore, for n large enough, we have

C(n) R(n) ≥ αn s+1 (s + 1) s r,...,r r s/r n 2 (s/r)!n s+1 ≥ ( α 2 ) s+1 n 2 r s/r (r!) s/r (s/r)! .
Taking logarithms in the last expression we obtain Let G be a graph in B n ⊆ B n . Choose a set of s + 1 pendant vertices v 1 , . . . , v s+1 in G, delete the edges joining the v i to the rest of the graph, and make a copy of the following graph F with the v i : first, as before, choose one special vertex, call it v 1 , and make it adjacent to all other v i . Group the remaining v i (all except for v 1 ) into groups of size r 1 = log s/ log ( ) s (we ignore rounding issues, taking care of them below). Choose in each of the s/r 1 groups a center vertex. Call all center vertices to be vertices at level 1. Iteratively, for i = 1, . . . , -2, do the following: group each group of size r i -1 (from each group we eliminate the center vertices at level i) into subgroups of size r i+1 = log (i+1) s/ log ( ) s. Choose in each subgroup a new center vertex, and call all center vertices chosen in this step to be vertices at level i + 1. Connect each center vertex at level i with all center vertices at level i + 1 resulting from subgroups of the group of vertex i. Connect all center vertices at level -1 with the remaining vertices of its corresponding subgroup (those vertices not chosen as centers).

(1 + o( 1
Observe that the graph F does not contain a C 2 +1 , since in the construction we add a forest of maximum path length 2( -1) to a star centered at v 1 , and thus the maximum cycle length is 2 .

Next select a vertex u of G different from the v i and make it adjacent to v 1 . The graph G constructed in this way belongs to G n , and has the same number of vertices as G. As before, we count the number of different graphs obtained by applying this construction to one graph of B n . We obtain at least

n 2 αn s+1 (s + 1) s r1,...,r1 -2 i=1 ri-1 ri+1,...,ri+1 s/ri(1+βi) (r i -1) s/ri(1+βi) ( s r1 )! -2 i=1 (( ri-1 ri+1 )!) s/ri(1+βi)
many graphs, where the β i = o(1) take into the account rounding issues and also the fact that in the ith step only r i -1 vertices are split into subgroups of size r i+1 (for example, we approximate s(r1-1) r1r2 by s r2 ; β 2 accounts for the difference. Indeed, even for the last term β -2 the error term is bounded from above by

-3 i=1 1 ri = o(1)
. By the same argument as in the proof of 2., a new graph can have at most n s+1 preimages. Thus, for n sufficiently large (the factors r s/ri i in the denominator are a lower bound corresponding to the fact that the factors r i in the numerator do not exactly cancel), we have

C(n) R(n) ≥ 1 2 n( 1 2 α) s+1 ((r 1 -1)!) s/r1 (r 1 !) s/r1 ( s r1 )!(r -1 )! s/r -1 (1+β -1 ) -2 i=2 r s/ri i -2 i=1 (( ri-1 ri+1 )!) s/ri(1+βi)
.

Taking logarithms, we obtain

(1 + o(1)) log n + s log(r 1 -1) -s log r 1 - s r 1 log s r 1 -s log r -1 - -2 i=1 s r i r i -1 r i+1 log r i -1 r i+1 .
Using s log(r 1 -1) = s log(r 1 ) + s log(1 -1/r 1 ) and s ri ri-1 ri+1 log ri-1 ri+1 ≤ s ri+1 log r i , we get that this expression is at least

(1 + o(1)) log n - s r 1 log s r 1 -s log r -1 - -2 i=1 s r i+1 log r i . (1)
Plugging in the values r i = log (i) s/ log ( ) s, all but the first term are (1 + o( 1))s log ( ) s, and thus, plugging in the value s = c log n/ log ( +1) n, for c < 1/ , the expression in (1) tends to infinity.

Remark. The 2-connected graphs which are a minor of some F n consist just of a cycle and some chords, all of them incident to the same vertex. In particular, if we forbid the graph consisting of a cycle of length six v 1 , v 2 , v 3 , v 4 , v 5 , v 6 and the chords v 1 v 3 and v 4 v 6 , the condition of part 1 of Theorem 3 still holds, and the conclusion that w.h.p. ∆ n ≥ c log n follows. The same also holds when forbidding the 6-cycle together with the chords

v 1 v 3 , v 3 v 5 , v 5 v 1 .
3 Characterization of 2-connected graphs in Ex(C 5 ), Ex(C 6 ) and Ex(C 7 )

In this section we determine all 2-connected graphs in the classes Ex(C 5 ), Ex(C 6 ) and Ex(C 7 ). This is an essential ingredient for the proofs in the next section. As usual, K 2,n is the complete bipartite graph with partite sets of size 2 and n. Recall that K + 2,n denotes the graph obtained from K 2,n by adding an edge between the two vertices of degree n. We have the following:

Lemma 4. The only 2-connected graphs in Ex(C 5 ) are K 3 , K 4 , K 2,m and K + 2,m , for m ≥ 2.
Proof. Let G be a 2-connected graph in Ex(C 5 ). If G has at most three vertices, then it has to be K 3 .

Otherwise, if G has exactly four vertices, then it is either C 4 , K 4 minus one edge, or K 4 . Otherwise, suppose that G has at least 5 vertices. Let v, v 1 , v 2 , v 3 be the vertices in cyclic order of a C 4 in G. Assume without loss of generality that v has another neighbor different from v 1 and v 3 , and also different from v 2 . Observe that a cannot be adjacent to v 1 or v 3 , since this would create a C 5 . By 2-connectivity, there must exist a path from

a to v 2 containing none of v, v 1 , v 3 . Since G is in Ex(C 5 ), it follows that a is adjacent to v 2 .
This holds for all neighbors of v different from v 2 . Thus, they must form an independent set, and we obtain a copy of K 2,m . The only edge that can be added while staying in Ex(C 5 ) is the edge vv 2 , giving rise to

K + 2,m .
For s, t ≥ 0, define the graph H 2,s,t , obtained by identifying a vertex v of degree s + 1 in K 2,s+1 and a vertex of degree t + 1 in K 2,t+1 , and by adding an edge between the other vertices v 2 and v 3 of degree s + 1 and t + 1, respectively. Note that v has thus at least one common neighbor with v 2 , call it v 1 , and at least one common neighbor with v 3 , call it v 4 (see Figure 1). We denote by H * 2,s,t any graph obtained from H 2,s,t by adding a subset of the edges between vertices x and y with x, y ∈ {v, v 1 , v 2 , v 3 , v 4 }, unless they are creating a cycle of length 6 or longer (see Figure 1). Observe that the subset of edges allowed depends on the fact whether s or t are different from 0 or not; only in the case s = t = 0 all edges between special vertices can be added, yielding K 5 .

s t v v1 v2 v3 V4 Figure 1:
The graph H 2,s,t with the notation as in Lemma 5, and with two optional edges (dashed)

Lemma 5. The only 2-connected graphs in Ex(C 6 ) are those in Ex(C 5 ), the graphs H 2,s,t , and any graph of the form H * 2,s,t , for s, t ≥ 0.

Proof. Let G be a 2-connected graph in Ex(C 6 ). If G is in Ex(C 5 ), we apply the previous lemma. If G contains C 5 and has exactly 5 vertices, then G is either H 2,0,0 or H * 2,0,0 . Otherwise let v, v 1 , v 2 , v 3 , v 4 be the vertices in cyclic order of a C 5 in G (see Figure 1). Call these vertices special. Observe that except for possible edges between neighbors of v that are both special vertices, N (v) is an independent set. Consider a non-special neighbor a of v. As in the proof of Lemma 4, by 2-connectivity, a is adjacent to either Remark. When later we refer to graphs H 2,s,t or in H * 2,s,t , with v 3 or v 4 playing the role of v, they will be denoted as H 2,s,t and H * 2,s,t . Define the graph S s,t,u,w to be the graph constructed as follows: start with a 6-cycle whose vertices in cyclic order are v, v 1 , v 2 , v 3 , v 4 , v 5 , and call these vertices special. In addition there are w ≥ 0 vertices connecting v 2 and v 4 , s ≥ 0 vertices connecting v with v 2 , t ≥ 0 vertices connecting v with v 4 , and u ≥ 0 vertices connecting v with both v 2 and v 4 (in all cases excluding special vertices). Define then by S * s,t,u,w any graph obtained by possibly adding any of the edges between special vertices without creating a cycle of length 7 or more, see Figure 2. Finally, let V s,t,E the following class of graphs: start with a 6-cycle v, v 1 , v 2 , v 3 , v 4 , v 5 , again called special vertices. There is a set A of s ≥ 0 vertices connecting v with v 2 , and a set B of t ≥ 0 vertices connecting v with v 4 (always excluding special vertices).

v 2 or v 3 , but not both. Let A = N (v) ∩ N (v 2 ) -{v 1 }, B = N (v) ∩ N (v 3 ) -{v 4 }, s = |A|,
In addition, there is the following set of connections between v and v 3 (not including vertices in A or B or special vertices) specified by K = {e 1 , e 2 , e 3 , e 4 , e 5 , e 6 }. There are e 1 ≥ 0 vertices connecting v with v 3 , and e 2 pairs of vertices which are adjacent to each other, and both are adjacent to both v and v 3 . Furthermore, there are e 3 disjoint graphs K 2,qi (for i = 1, . . . , e 3 ) emanating from v 3 , and the other vertex of degree q i is connected to v. For e 4 , the construction is the same, except that for these graphs also the edge between v 3 and the other vertex of degree q i is present. Finally, there are e 5 and e 6 disjoint graphs K 2,qi which are as the graphs e 3 and e 4 , but with the roles of v 3 and v exchanged. For further reference, call the graphs of group e 3 and e 4 double stars of degree q i emanating from v 3 (for i = 1, . . . , e 3 ), and those of group e 5 and e 6 double stars emanating from v of degree q i . All vertices appearing in any of the six groups are disjoint and we refer to them as external vertices. Finally, V * s,t,E is the class of graphs obtained by possibly adding any of the edges between special vertices without creating a cycle of length 7 or more (see Figure 3 for an example). Lemma 6. The only 2-connected graphs in Ex(C 7 ) are those in Ex(C 6 ), the graphs S s,t,u,w , V s,t,E and the corresponding graphs

S * s,t,u,w , V * s,t,E . Proof. Let G be a 2-connected graph in Ex(C 7 ). If G is in Ex(C 6 )
, we apply the previous lemma. If G contains C 6 and has exactly 6 vertices, then G = S 0,0,0,0 or G = S * 0,0,0,0 . Otherwise, let v, v 1 , v 2 , v 3 , v 4 , v 5 be the vertices in cyclic order of a C 6 in G, again called special. We distinguish two cases now. In the sequel all new vertices considered are not special vertices. Case 1: There is no other vertex a with the property that there are two internally vertex-disjoint paths of length three from v to a. We distinguish between two subcases. Case 1.1: Suppose first that there exist u ≥ 1 vertices a ∈ N (v) that are adjacent to both v 2 and v 4 . Observe that the existence of such a vertex a implies that no external vertex e can be present in G, as otherwise one Figure 3: The graph V s,t,E with the notation as in Lemma 6 (e 1 = e 2 = 1, e 3 = e 4 = 0, e 5 = e 6 = 1 with corresponding degrees q 1 and q 2 ), and with two optional edges (dashed)

would have a cycle of length at least 7 (namely, v,v 1 ,v 2 ,a,v 4 ,v 3 ,e,v). Hence, all non-special neighbors of v can be partitioned into three sets A, B and C, where A is the set of s ≥ 0 vertices connected only with v 2 , B is the set of t ≥ 0 vertices connected only v 4 , and C is the set of u ≥ 1 vertices connected to both v 2 and v 4 . This corresponds exactly to the graph S s,t,u,w with w = 0. It is easy to check that except for edges yielding a graph in S * s,t,u,0 , no edge can be added, as otherwise a 7-cycle would be generated (see Figure 2). Case 1.2: Suppose that there is no vertex a ∈ N (v) adjacent to both v 2 and v 4 . Let A be the neighbors of v connecting v with v 2 , and let B be the neighbors of v connecting v with v 4 . Let s = |A| and t = |B|. External vertices connecting v with v 3 are now possible. Note first that none of them can be adjacent to a special vertex except for v,v 2 in the case of A and except for v,v 4 in the case of B, neither to another vertex in A or B. There can be e 1 vertices connecting v with v 3 , and e 2 pairs of vertices, adjacent to each other, both adjacent to v and v 3 . Also, we might have e 3 (e 4 , respectively) double stars of degree q i ≥ 0 emanating from v 3 , where the other vertex of degree q i is also adjacent to v (in the case of the e 4 vertices, the edge between v 3 and the other vertex of degree q i is also present). Also, the roles of v 3 and v can be interchanged, yielding e 5 double stars (e 6 , respectively) of degree q i emanating from v (in the case of the e 6 stars, the edge between v and the other vertex of degree q i is added as well; observe that in the case of the e 5 double stars we may assume q i ≥ 2, as otherwise these vertices appear already among the e 3 stars). The six groups are disjoint and there can be no other edge between external vertices. Thus, denoting K = {e 1 , . . . , e 6 }, we obtain a graph in V s,t,E . As before, no other edge except for edges yielding a graph in V * s,t,E can be added (see Figure 3). Case 2: There exists at least one more vertex a such that there are two internally vertex-disjoint paths of length three from v to a. These paths must be of the form v, v 1 , v 2 , a and v, v 5 , v 4 , a (if for example instead of the edge vv 1 there would be an edge vz for some other vertex z, there would be a path of length 6 going from z,v,v 5 , . . . , v 1 , which, by 2-connectivity, would give a cycle of length at least 7). We suppose there are w ≥ 1 such vertices a with such paths. Observe that the existence of such a vertex a implies that no external vertex e can be present in G, as otherwise one would have a cycle of length at least 7 (namely, the cycle v,v 1 ,v 2 ,a,v 4 ,v 3 ,e,v). All non-special neighbors of v can thus be partitioned into three sets A, B, and C, where A are those connected only with v 2 , B those connected only with v 4 , and C those connected both with v 2 and v 4 . We let s = |A|, t = |B|, u = |C|. Let W be the vertices which are neither neighbors of v nor special vertices, and w = |W |. Again it can be checked that they all are such that there are two internally vertex-disjoint paths of length three from v to them, thus yielding a graph in S s,t,u,w . As before, except for edges yielding a graph in S * s,t,u,w , no other edge can be added.

Remark. When later we refer to graphs in S s,t,u,w or V s,t,E (or to the corresponding graphs in S * s,t,u,w or V * s,t,E ), where either v 2 , v 3 , v 4 or any of the external vertices of high degree play the role of v, they will be denoted as S s,t,u,w and V s,t,E ( S * s,t,u,w and V * s,t,E , respectively).

Upper bounds

We make repeated use of the following well-known lemma, whose proof is standard and therefore omitted.

Lemma 7. Let n 1 , . . . , n r be positive integers such that i n i = N for some constant N . Then i n i log n i is minimized when all n i are equal to N/r or N/r .

Also, we need the following lemma, whose proof is a straightforward generalization of Lemma 2.2 from [START_REF] Mcdiarmid | On the maximum degree of a random planar graph[END_REF].

Lemma 8. Let G = Ex(H 1 , . . . , H k ),
where the H i are 2-connected. Then w.h.p. each vertex in a graph in G n is adjacent to at most 2 log n/ log log n pendant vertices.

As in Section 2, we illustrate our technique to reprove in a simpler way the following known result (see [START_REF] Moon | On the maximum degree in a random tree[END_REF][START_REF] Carr | The maximum degree in a random tree and related problems[END_REF]), complementing Lemma 2.

Lemma 9. Let > 0 be any constant. In the class of forests, w.h.p.

∆ n ≤ (1 + ) log n log log n .
Proof. Let G be the class of forests and G n the class of forests with n vertices. Let B n ⊆ G n now denote the set of bad graphs with

∆ n > (1 + ) log n log log n ,
and suppose for contradiction that |B n | ≥ µ|G n | for some µ > 0, infinitely often. Let B n ⊆ B n be the class of graphs that has at least αn pendant vertices, and which is such that every vertex is adjacent to at most 2 log n/ log log n pendant vertices. By Lemma 1 and Lemma 8,

|B n | = (1 + o(1))|B n |.
Let G be a graph in B n , and let v be a vertex with degree k > (1 + ) log n log log n . Since G ∈ B n , there are at least (αn -2 log n/ log log n) ≥ 2αn/3 pendant vertices not adjacent to v. Let c = min( /2 1+ , α/3) and choose a set of ck ≤ 2αn/3 pendant vertices not adjacent to v and delete their adjacent edges. Maintain vertex v and delete all its adjacent edges. Attach the ck chosen vertices to v, and construct many new graphs by attaching the former k neighbors of v in all possible ways to any of the previously added ck vertices. More precisely, a fixed new graph is obtained by choosing for each of the former k neighbors of v, its corresponding vertex among the ck vertices previously added, and then connecting to it by an edge. Observe that the new vertices have been added in a tree-like way, and hence the new graph is still in G n . Since we are interested in an asymptotic result, we may ignore ceilings from now on. The number of graphs constructed in this way is at least 2αn/3 ck (ck) k . From how many graphs may the newly constructed graph G come? One has to guess v, and then reattach the ck pendant vertices, giving rise to at most n ck+1 choices. Hence, Recall that a block H is a maximal connected subgraph without having a cut-vertex. Note that if H is a block, either H is 2-connected or H has at most 2 vertices. Now we proceed to prove new results. In order to prove an upper bound for ∆ n in a class G n , the basic idea is to generalize the previous proof. Take a graph G in G n whose maximum degree is too large (a bad graph), and let v be a vertex with large degree. Consider the blocks containing v and their contribution to the degree of v: the lemmas in Section 3 tell us all possible 2-connected components that can occur, which therefore, together with isolated vertices and isolated edges, tell us all blocks that can occur. We classify the blocks according to whether this contribution is larger or smaller than a suitable threshold. If B is a block with a vertex b of large degree t, remove the edges connecting b to its neighbors b 1 , . . . , b t , take ct pendant vertices (where c < 1 is a suitable constant), isolate them and make them adjacent to v, and connect arbitrarily each of the b i to any of the new ct vertices. Whatever was attached to the b i remains untouched. When necessary, we add a few extra vertices and edges to ensure unique reconstruction. Blocks with small degree are not dismantled. This construction guarantees that we stay in G n . Double counting is used again to show that the proportion of bad graphs goes to 0 as n goes to infinity.

C(n) R(n) ≥ 2αn/3 ck (ck) k n ck+1 ≥ (α/3) ck (ck) k n(ck)! . Note that (ck) k /(ck)! > (ck) (1-c)k . Taking logarithms, this gives log C(n) R(n) ≥ (1 -c)k log k -log n + O(k) ≥ (1 -c)(1 + )(1 + o(1)) log n -log n,
In the next proof we do not need all the power of this method, since blocks in Ex(C 4 ) have bounded degree, but already in the class Ex(C 5 ) there are blocks of arbitrary high degree.

Lemma 10. Let > 0 be any constant. In the class Ex(C 4 ), w.h.p.

∆ n ≤ (2 + )
log n log log n .

Proof. We first observe that the only blocks in Ex(C 4 ) are isolated vertices, edges and triangles. Let G = Ex(C 4 ) and let B n ⊆ G n now denote the set of bad graphs with

∆ n > (2 + ) log n log log n .
As before, let B n ⊆ B n be the class of graphs that has at least αn pendant vertices, and which is such that every vertex is adjacent to at most 2 log n/ log log n pendant vertices. Once again, by Lemma 1 and Lemma 8,

|B n | = (1 + o(1))|B n |.
Let G be a graph in B n and let v be a vertex with degree k > (2 + ) log n log log n . As before, there are at least (αn -2 log n/ log log n) ≥ 2αn/3 pendant vertices not adjacent to v. Let c = min( /3 1+( /2) , α/3). Let r be the number of blocks incident to v and observe that (k/2) ≤ r ≤ k, since the only blocks are edges and triangles. Choose a set of cr ≤ 2αn/3 pendant vertices not adjacent to v and delete their adjacent edges. Maintain vertex v and delete all its adjacent edges. Attach the cr chosen vertices to v, and construct, as before, new graphs by attaching the roots of all r blocks in all possible ways to any of the previously added cr vertices. Ignoring ceilings, the counting is as before: the number of graphs constructed in this way is at least 2αn/3 cr (cr) r , and for recovering G, one has to guess v, then reattach the cr pendant vertices, giving rise to at most n cr+1 choices. Hence,

C(n) R(n) ≥ 2αn/3 cr (cr) r n cr+1 ≥ ( 1 3 α) cr (cr) r n(cr)! .
Note that (cr) r /(cr)! > (cr) (1-c)r . Thus, taking logarithms, this gives log

C(n) R(n) ≥ (1 -c)r log r -log n + O(r) ≥ (1 -c)(k/2) log k -log n + O(k),
which again tends to infinity by our choice of c. Hence,

|B n | = o(|G n |).
Theorem 11. Let > 0 be any constant. In the class Ex(C 5 ), w.h.p.

∆ n ≤ (1 + ) log n log log log n .
Proof. Let G = Ex(C 5 ) and let B n ⊆ G n the graphs with

∆ n > (1 + ) log n/ log log log n.
Assume for contradiction that there is some constant µ such that |B n | ≥ µ|G n | infinitely often. Once more, let B n ⊆ B n be the class of graphs that has at least αn pendant vertices, and which is such that every vertex is adjacent to at most 2 log n/ log log n pendant vertices. Again, we have

|B n | = (1 + o(1))|B n |.
Let G be a graph in B n and let v be a vertex of G such that k = deg(v) > (1 + ) log n/ log log log n. Since G ∈ B n , at least (αn -2 log n/ log log n) ≥ 2αn/3 pendant vertices are not adjacent to v. The strategy of the proof is as follows. We partition the blocks incident with v according to their type and to their contribution to the degree of v. Those with degree smaller than a threshold can be safely ignored for the asymptotics. Those of large degree, which by Lemma 4 are isomorphic to either K 2,t or K + 2,t , are used to produce many new graphs as in the proofs for the lower bounds. Then a double counting argument is used again to show that |B n |/|G n | → 0. The strategy for Ex(C 6 ) and Ex(C 7 ) is very similar but there are more types of blocks to consider, making the situation a bit cumbersome.

Let us proceed with the proof. We partition the blocks attached to v. Using Lemma 4, they can be partitioned into the following classes: and that r i < ki log log k log k for i = 2, 3.

In order not to run out of pendant vertices, let now c = min( /2 1+ , 1 4 α). From G we construct now a class of graphs, as follows.

• Choose a set U of h (h will be determined below) pendant vertices and delete their adjacent edges.

Maintain vertex v and delete all its adjacent edges. Choose three vertices from U , eliminate them from U and make them neighbors of v. Call them w.l.o.g. v 1 , v 2 , v 3 and assume that their labels are sorted increasingly. Choose cr 1 vertices from U , eliminate them from U and make them neighbors of v 1 . Attach the roots of all blocks of class 1 in all possible ways to any of the previously added cr 1 vertices.

• Choose r 2 vertices from U , eliminate them from U (each of them representing a block of class 2) and make them neighbors of v 2 . For each block of class 2 of type K 2,ti (i = 1, . . . , r 2 ) choose 1 + ct i vertices from U , eliminate them from U , and connect all of them to the previously added vertex that represents the i-th block of this class. Let x i be the vertex with smallest label among the 1 + ct i vertices added (i = 1, . . . , r 2 ). For each block K 2,ti of G, define z 0 i to be the other vertex apart from v of degree t i , and let z 1 i , . . . , z ti i the vertices of degree 2. In our construction, we delete all edges belonging to the original block and we add the following edges: z 0 i is connected with x i , and we connect each of the vertices z j i (j ≥ 1) in all possible ways to any of the previously added ct i vertices excluding x i .

• For blocks of class 3, do the analogous steps as for blocks of type 2.

Observe that the new vertices have been added in a tree-like way in this construction, that is, we have not created any cycle that did not exist in the original graph. In particular, if G ∈ Ex(C 5 ), so are all the newly constructed graphs. Also observe that the number of pendant vertices h used satisfies h ≤ ck(1 + o( 1)) < αn/3. We proceed to count the number of different graphs we obtain by applying this construction to one graph of B n . To simplify notation, we will ignore ceilings. We obtain at least 2αn/3 h h cr 1 , r 2 , ct 1 + 1, . . . , ct r2 + 1, r 3 , ct 1 + 1, . . . , ct r3 + 1, 3

r 2 !r 3 ! × (cr 1 ) r1 r2 i=1 (ct i ) ti r3 i=1 (ct i ) t i (2)
many graphs, since there are at least 2αn/3 h ways to choose h pendant vertices not incident to v, which then have to be partitioned into the different groups explained before (yielding the multinomial coefficient). The factors r 2 ! and r 3 ! come from the fact that blocks of class 2 and 3 are distinguishable because of their labels, hence any permutation of the r 2 and r 3 vertices will give rise to different graphs. The last group of three vertices in the multinomial coefficient corresponds to the vertices v 1 , v 2 , v 3 (there is no 3!, since the roles of these vertices are determined by their labels). The remaining factors count the possible ways to do the connections between the r 1 vertices and the added cr 1 vertices, between the added the t i vertices and the added ct i vertices, and between the t i and the ct i .

Since different original graphs may give rise to the same new graph, we have to divide the total number of constructions by the number of preimages of a new graph. This number is as before at most n • n h , since we first must guess the vertex v of the original graph (this gives the factor n) and then we have to redistribute the h newly added vertices as pendant vertices (for those we have at most n h choices).

Our goal is to show that the total number of newly constructed graphs divided by the number of preimages of a new graph tends to infinity as n increases, hence contradicting the assumption that |B n | ≥ µ|G n | for infinitely many values of n.

Note that the following expression is a lower bound of ( 2).

(1/2) k log log k/ log k 1 3 (α -c)n h (cr 1 ) (1-c)r1 r2 i=1 (ct i ) (1-c)ti r3 i=1 (ct i ) (1-c)t i ,
where we have used that h = ck(1 + o( 1)), k < n so that 1 6 ( 2 3 αn)!/( 2 3 αn -h)! is bounded from below by ( 13 (α -c)n) h ; we also used that for any g > 0 it holds that (cg) g /(cg)! ≥ (cg) (1-c)g , and that for any g such that cg ≥ 3 it holds that (cg) g /(cg+1)! ≥ (cg) (1-c)g , and for smaller values of cg, (cg) g /(cg+1)! ≥ 1 2 (cg) (1-c)g , giving the additional (1/2) k log log k/ log k leading factor.

We now divide by the number of preimages n • n h , and then we take logarithms. Hence, noting that

k 2 = r2 i=1 t i and k 3 = r3 i=1 t i , we obtain -log n + o(k) + O(h) + (1 -c)r 1 log r 1 + O(r 1 ) + (1 -c) r2 i=1 t i log t i + O(k 2 ) + (1 -c) r3 i=1 t i log t i + O(k 3 ).
By Lemma 7, r2 i=1 t i log t i is minimal when all t i are equal, and the same applies to the t i . Hence, the previous expression is bounded from below by

-log n + O(k) + (1 -c + o(1)) r 1 log r 1 + k 2 log k 2 r 2 + k 3 log k 3 r 3 . (3)
Now, letting k i = β i k for i = 1, 2, 3, we obtain

r 1 ≥ k 1 log log k log k = β 1 k log log k log k ,
and thus

r 1 log r 1 ≥ β 1 k log log k log k (log k + o(log k)) = β 1 k log log k(1 + o(1)). Also, recall that r 2 ≤ k2 log log k log k , so that k 2 r 2 ≥ log k log log k ,
and the term k 2 log k2 r2 in (3) is at least

k 2 log k 2 r 2 ≥ k 2 log log k(1 + o(1)) = β 2 k log log k(1 + o(1)).
By the same argument,

k 3 log k3 r3 ≥ β 3 k log log k(1 + o(1)). As β 1 + β 2 + β 3 = 1,
one of the β i has to be at least 1 3 , hence we can safely ignore the term O(k) in ( 3). The expression in ( 3) is thus bounded from below by (1 + o( 1)

)(1 -c)k log log k -log n,
which by our choice of c tends to infinity, as desired.

Theorem 12. Let C > 0 be a sufficiently large constant. In the class Ex(C 6 ), w.h.p.

∆ n ≤ C log n log log log n .

Proof. The proof starts as for Ex(C 5 ). Let G = Ex(C 6 ) and let B n ⊆ G n the class of graphs with ∆ n > C log n/ log log log n.

We assume for contradiction that there is some constant µ such that |B n | ≥ µ|G n | infinitely often. Let also B n ⊆ B n be the class of graphs that has at least αn pendant vertices, and which is such that every vertex is adjacent to at most 2 log n/ log log n pendant vertices. Again, we have Choose a set U of h pendant vertices not incident to v and delete their adjacent edges. Maintain vertex v and delete all its adjacent edges. We now have a bounded number N of subclasses represented by classes 1 to 4 and the possible cases in the definition of H * 2,s,t , H 2,s,t and H * 2,s,t . For each subclass i, let r i be the number of blocks of subclass i incident with v. For each i, take a pendant vertex w i from U and make it adjacent to v, and sort the w i in increasing order of the labels. For each i (except for class 1), take r i pendant vertices from U and make them adjacent to w i . Let c = min(1 -3N C , 1 4 α). Note that for C < 3N the expression for c is negative, so the assumption that C is sufficiently large in particular also implies that C ≥ 3N .

|B n | = (1 + o(1))|B n |. Let G
For blocks in classes 1 and 2 (they give rise to r 1 ,r 2 , r 3 ), the r i play the same role as in the proof of Theorem 11, and we append the same construction as there.

For blocks of type H 2,s,t the construction is very similar; they behave like the graphs K 2,s , but with two sets, of size s and t, of vertices of degree two. For each block of type H 2,s,t , we add two new sorted vertices from U and make them adjacent to the vertex representing the block. Take 2 + cs and 2 + ct vertices from U (ignoring ceilings from now on) and connect them, respectively, to the two previously added vertices. Let x 0 , x 1 and y 0 , y 1 , respectively, be the vertices with smallest labels (in this order) among the 2 + cs and the 2 + ct added vertices. Delete all edges belonging to the original block and attach the s vertices to the newly added cs vertices (excluding x 0 and x 1 ) in all possible ways, and do the same for the t vertices (excluding y 0 and y 1 ). Also, connect x 0 to v 1 (notation as in Lemma 5), x 1 to v 2 , and y 0 to v 3 , y 1 to v 4 . For blocks of type H * 2,s,t the construction is exactly the same; the fact that the different subclasses are identified by the labels as well as the special role of v 1 , v 2 , v 3 , v 4 guarantees unique reconstruction. Finally, consider blocks of type H 2,s,t , and assume without loss of generality that v 2 plays the role of v. In this case we add only cs + 4 vertices from U and make them adjacent to the vertex representing the block. Let x 0 , x 1 , x 2 and x 3 be the vertices with the four smallest labels (in this order). Delete all edges in H 2,s,t emanating from v and v 2 , all edges between special vertices, and connect all the s non-special neighbors of v 2 to the cs vertices (excluding x 0 ,x 1 ,x 2 and x 3 ) in all possible ways. Connect x 0 to v, x 1 to v 3 , x 2 to v 1 , and x 3 to v 4 . As before, the same construction is applied for H * 2,s,t (the only difference being that all optional edges are deleted as well); as before, the special roles and the different labels of different subclasses provide all information for unique reconstruction.

Since no new cycle is created, given v and the new graph, we can uniquely determine the original graph it comes from. Observe also that we used only h ≤ ck(1 + o(1)) pendant vertices. As before, we count the number of different graphs we obtain by applying this construction, yielding similar multinomial coefficients and other factors. Dividing by the number of preimages of a new graph, which is at most n h+1 , and taking logarithms, we obtain

-log n + o(k) + O(h) + (1 -c)r 1 log r 1 + O(r 1 ) + (1 -c) r2 j=1 (s j ) 2 log(s j ) 2 + O(k 2 )+ (1 -c) r3 j=1 (s j ) 3 log(s j ) 3 + O(k 3 ) + (1 -c) i≥4,i∈T ri j=1 (s j ) i log(s j ) i + (1 -c) i≥4,i∈T ri j=1 (t j ) i log(t j ) i + O( i≥4 k i ),
where we denote by k i the total contribution of blocks of subclass i to the degree of v, and by (s j ) i and (t j ) i the corresponding sizes of the jth block of subclass i ≥ 2; both sets T and T contain all indices of subclasses belonging to blocks H 2,s,t or H * 2,s,t , T contains in addition to this all indices of subclasses of blocks of type H 2,s,t and H * 2,s,t with v 2 playing the role of v, and T contains in addition to this all subclasses of blocks of type H 2,s,t and H * 2,s,t with v 3 playing the role of v. This distinction is needed since in the cases of H 2,s,t and H * 2,s,t only one of the two sums above has to be counted. Suppose w.l.o.g. that the contribution of all (t j ) i to the degree of v is at most k/2, and we may ignore this contribution above. Define then for 1 ≤ i ≤ 3, k i = k i , and for i ≥ 4, let k i = ri j=1 (s j ) i . Note that k i counts the contribution of the i-th subclass to the degree of v coming from the (s j ) i only. Clearly, k i ≤ k i and by assumption i≥1 k i ≥ k/2. By Lemma 7, the previous expression is at least

-log n + O(k) + (1 -c + o(1))(r 1 log r 1 + i≥2 k i log k i r i ). (4)
Since i≥1 k i ≥ k/2, there exists some 1 ≤ i ≤ N with k i ≥ k/(2N ). If this is true for i = 1, then

r 1 log r 1 ≥ k 1 log log k log k (log k 1 + o(log k 1 )) = k log log k 2N (1 + o(1)). Otherwise, if i ≥ 2, since k i ri ≥ log k 2N log log k , as before, k i log k i ri ≥ k log log k 2N (1 + o(1)
). Thus, by our choice of c, for C sufficiently large, (4) tends to infinity as desired.

In the class Ex(C 7 ), the right order of magnitude of the expected maximum degree changes, compared to Ex(C 5 ) and Ex(C 6 ). Before going into the proof, we give some intuition about the different behavior in Ex(C 7 ). The existence of a component V s,t,E as described in Lemma 6, and in particular the existence of t stars of different degrees q i inside one block, gives rise to new constructions. In order to ensure many constructions, both for the number of stars t (call this the first level), as well as for their degrees q i (call this the second level), choices have to be made: if there were few stars of a high degree, only on the second level many choices can be made, but if, however, there are many stars of small degree, on the first level many choices can be made. For a medium number of stars with medium degree, on both levels some choices can be made. These two choices imply that the definition of small has to be changed, and the trade-off between the contribution of small blocks and other larger blocks (which give different types of contributions in the proofs) gives rise to an additional application of the logarithm. We now state the result for this class.

Theorem 13. Let C > 0 be a sufficiently large constant. In the class Ex(C 7 ), w.h.p. Choose a set of U of h pendant vertices not incident to v and delete their adjacent edges. Maintain vertex v and delete all its adjacent edges. We still have a bounded number of subclasses N represented by the different classes and the possible optional edges. For each subclass i, let r i be the number of blocks of subclass i incident with v. For each i, take a pendant vertex w i from U and make it adjacent to v, and sort the w i in increasing order of the labels. For each i (except for those subclasses belonging to class 1), take r i pendant vertices from U and make them adjacent to w i . Let c = min(1 -9N C , 1 4 α). As before, we assume that C is large enough and in particular C ≥ 9N , so that c is positive.

∆
For blocks in classes 1 and 2, we proceed as in the proof of Theorem 11 and Theorem 12. We ignore ceilings and justify after the constructions that they may be safely disregarded. For blocks S s,t,u,w and S * s,t,u,w the construction is very similar as before: for the new vertex b (among the r i added ones) representing a block of such a subclass, take three sorted vertices b 1 , b 2 , b 3 from U and make them adjacent to b. Take 5 + cs, (ct, cu, respectively) vertices from U , and attach them to the first of these sorted vertices (second and third, respectively). Denote by x 1 ,x 2 ,x 3 ,x 4 ,x 5 the vertices with smallest labels (in this order) of the first group. Delete all edges from the original block except for the edges incident to the w vertices (excluding v,v 1 ,v 3 ,v 5 , if the edges are present) that are connected with both v 2 and v 4 . Append the special vertices v 1 , v 2 , v 3 , v 4 and v 5 to the vertices x 1 ,x 2 , x 3 , x 4 , x 5 in this order. Connect then the s vertices (which originally were adjacent to v and v 2 ) to the cs vertices of the first group (excluding x 1 , . . . , x 5 ) in all possible ways, and do the analogous construction for the t and u vertices. Note that this time we might construct cycles of length 6 (of the type b 1 , x 2 , v 2 , a, v 4 , x 4 ), where a is one of the w vertices connecting v 2 and v 4 , but by the special roles of special vertices unique reconstruction is still guaranteed.

For blocks of type V s,t,E and V * s,t,E , and its corresponding vertex b representing the block, take eight sorted vertices b 1 , . . . , b 8 from U and make them adjacent to b. Take ce 1 , ce 2 , ce 3 , ce 4 elements from U and add them to b 1 , b 2 , b 3 , b 4 , respectively. Take 5 + cs elements from U (call the vertices with the 5 smallest labels x 1 , . . . , x 5 , in this order, as before), make them adjacent to b 7 , and take ct elements from U and make them adjacent to b 8 . From the original block delete all edges emanating from v, v 2 , v 4 , all edges between special vertices, all edges going between v 3 and any of the e 1 , e 2 vertices of the first and second group of E.

For the e 3 graphs of the third group of E, for any i, 1 ≤ i ≤ e 3 , the edges between the vertices of degree q i (different from v 3 ) and its q i neighbors of degree 2 are retained, and all others are deleted, and analogously for the e 4 graphs of the forth group. For the e 5 and e 6 graphs of the fifth and sixth group of E, all edges of it are deleted if the vertex of degree q i (different from v) satisfies q i > log log log n log log log log n , otherwise all edges going between the vertex of degree q i (different from v) and its q i neighbors different from v and v 3 are retained and the others are deleted. Now, connect v 1 , . . . , v 5 with x 1 , . . . , x 5 . For the e 1 vertices originally connecting v and v 3 , connect them to the ce 1 vertices (which were attached to b 1 ) in all possible ways. For the e 2 pairs adjacent to each other and both connecting v and v 3 , connect the one with smaller label in all possible ways to the ce 2 vertices attached to b 2 (recall that the edge connecting such a pair is not deleted). For the e 3 and e 4 double stars K 2,qi , connect all vertices of degree q i (different from v 3 ) and its pending q i neighbors with the ce 3 and ce 4 vertices attached to b 3 and b 4 , respectively, in all possible ways. For the e 5 graphs K 2,qi emanating from v (of degrees q 1 , . . . , q e5 ), take c 2 e 5 vertices from U , attach them to b 5 , and connect each of the e 5 vertices z 1 , . . . , z e5 of degree q 1 , . . . , q e5 to the c 2 e 5 vertices in all possible ways. Then, for each of the z i (1 ≤ i ≤ e 5 ), do the following: if q i ≤ log log log n log log log log n , do nothing (recall that the neighbors of z i are still pending). Otherwise, take c 2 q i vertices from U and make them adjacent to z i . Connect each of the q i vertices (originally neighbors of z i ) in all possible ways to the newly attached c 2 q i vertices. The analogous construction is done for e 6 (with b 6 instead of b 5 ). Finally, connect the s vertices originally connecting v and v 2 (excluding special vertices) with the group of cs new vertices (excluding x 1 , . . . , x 5 ) attached to b 7 in all possible ways. Similarly, connect the t vertices originally connecting v and v 4 with the group of ct new vertices attached to b 8 in all possible ways. Here, the graph constructed is always a tree, and reconstruction is unique.

For blocks of type S s,t,u,w and S * s,t,u,w , the strategy is similar as before. Assume without loss of generality that v 2 plays the role of v. In this case we take three vertices from U (sorted) and make them adjacent to the vertex representing this block. Take 5 + cs new vertices from U , make them adjacent to the first one, then cu further ones, make them adjacent to the second one, and finally another cw, which are made adjacent to the third one. All edges are deleted except for edges between v 4 and its t non-special neighbors that were also connected with v. The 5 vertices of the first group with smallest labels are connected to special vertices, and the s, u and w neighbors of v 2 (except for special vertices) are, as before, connected in all possible ways with the cs, cu and cw vertices of the respective groups. Observe that the constructed graph is a tree.

For blocks of type V s,t,E and V * s,t,E , either of v 2 , v 3 , v 4 or any of the external vertices in double stars of degree q ≥ C log n log log log log n arising in the groups e 3 , e 4 , e 5 , e 6 may play the role of v. In all cases, edges between special vertices are always deleted. If v 3 plays the role of v, all edges between v 2 and its s neighbors that are connected with v, and all edges between v 4 and its t neighbors that are connected with v are retained; for the others deletion is as for V s,t,E and V * s,t,E with v 3 playing the role of v. In more detail, for each vertex b representing a block of such a subclass, six sorted vertices b 1 , . . . , b 6 from U are added, 5 extra vertices taking care of special vertices are attached to b 1 , say, and the previous constructions restricted to b 1 , . . . , b 6 with v 3 playing the role of v is performed. If v 2 or v 4 (assume v 2 without loss of generality) plays the role of v, all edges emanating from a neighbor of v 2 are deleted (in particular, all edges emanating from v 3 ). For each block of such a subclass with b the newly attached vertex representing the block of this subclass, add 5 + cs vertices to b. The 5 vertices with smallest labels (in order) are attached to v,v 1 ,v 3 ,v 4 and v 5 , respectively. The s vertices originally connected to v 2 are then connected in all possible ways to the cs vertices excluding the 5 special vertices. Note that cycles of length 6 such as b, x 2 , v, a, v 4 , x 4 , b with a being one of the t vertices connecting v with v 4 can occur and x 2 (x 4 , respectively) one of the special neighbors of b to which v (v 4 , respectively) is attached, but the special role of the special vertices still guarantees unique reconstruction. For the s edges emanating from v 2 the usual reconstruction is performed (again with 5 special vertices assuring unique reconstruction, and another cs vertices to which the s vertices may connect in all possible ways). If any of the external vertices a of degree q plays the role of v, say w.l.o.g. a neighbor of v, the procedure is very similar: all edges emanating from a neighbor of a, in particular all edges emanating from v, are deleted. Then, 5 + cq vertices are taken from U , and the q neighbors of a are connected in all possible ways to the cq new vertices (the 5 vertices take care of special vertices). Note that again cycles of length 6 can be constructed (in case a is a neighbor of v 3 ), but by the special roles of special vertices reconstruction is still unique.

Observe that the largest cycle created is of length at most 6, and in all cases the special vertices guarantee unique reconstruction. Observe also that the number of pendant vertices used is at most h = ck(1+o(1)): for contributions of type e 5 and e 6 in components V s,t,E ,V * s,t,E (and of type e 3 and e 4 in components V s,t,E , V * s,t,E with v 3 playing the role of v), at the first level c 2 e 5 vertices are used, and at the second level, at most c 2 e5 i=1 q i (1+o(1)) (note that ceilings may be safely disregarded, as only for sufficiently large q i these vertices are chosen), and since e 5 ≤ e5 i=1 q i , the total number is at most c e5 i=1 q i . For the other contributions it is obvious. As before, for each case we count the number of different graphs we obtain by applying this construction, yielding similar multinomial coefficients and other factors as before. Then we divide by the number of preimages of a new graph, which is at most n h+1 , and take logarithms. Similar calculations as before show that the most negative term is -log n, coming from the choice of the vertex v. Recall that N is the total number of subclasses. Now, if at least k/N of the degree of v is in blocks of size at most 1)), and for c as chosen and C large enough this is bigger than the (negative) term log n. Otherwise, suppose that at least k/N of the degree of v results from any fixed subclass of blocks excluding V s,t,E or V * s,t,E (and also excluding V s,t,E and V * s,t,E with v 3 playing the role of v). Letting r j denote the number of such blocks, by similar calculations as before, as there is only one level of choice, we obtain a positive term Θ(k log k rj ). Since r j ≤ k log log log k log k , Θ(k log k r j ) = Ω(k log log k), which is asymptotically bigger than log n. Hence, assume that k/N of the degree of v comes from a subclass j in V s,t,E or V * s,t,E (or V s,t,E and V * s,t,E with v 3 playing the role of v), and assume without loss of generality that it belongs to the class V s,t,E . Let again be r j ≤ k log log log k log k the number of blocks of this subclass. If at least k/(2N ) of the total degree comes from contributions of the groups of s, t, e 1 , e 2 , e 3 , e 4 in the blocks of V s,t,E , then, as before, only considering those terms, as there is one level of choice, we obtain a term Θ(k log k rj ) = ω(log n). Hence, we may assume without loss of generality that k/(4N ) of the total degree comes from contributions of group e 5 . Once more, we split this into two subcases: if at least k/(8N ) of the total degree comes from double stars K 2,q with q ≤ log log log n log log log log n , then at least z ≥ k log log log log n 8N log log log n such double stars K 2,q are needed. Denote by z i the number of double stars inside the ith block to z, for 1 ≤ i ≤ r j . Each such block gives a term z i log z i , and the total contribution is by Lemma 7 minimized when the number of double stars is equally split among all blocks. Assuming the worst case of r j = k log log log k log k and z = k log log log log n 8N log log log n , the total contribution is thus at least which for our choice of c and C large enough is bigger than log n. If on the other hand at least k/(8N ) of the total degree comes from double stars K 2,q with q > log log log n log log log log n , then first observe that the number z of double stars K 2,q contributing to the total degree satisfies z ≤ k log log log log n 8N log log log n . Recall that q i denotes the degree of the ith double star for 1 ≤ i ≤ z. Clearly, z i=1 q i ≥ k/(8N ). Each such double star gives on the second level of choice rise to a term (1 -c)q i log q i . Assume again the worst case z i=1 q i = k/(8N ) and z = k log log log log n 8N log log log n . This contribution is, once more by Lemma 7, minimized if the contribution is split evenly, that is, q i = k 8N z , and in this case we obtain

Conclusion and open problems

Our work suggests several conjectures and open problems.

1. We conjecture that the lower bound

∆ n ≥ c log n log ( +1) n
for the class Ex(C 2 +1 ) is of the right order of magnitude. The proofs for Ex(C 5 ) and Ex(C 7 ) seem difficult to adapt for arbitrary .

2. We conjecture that the asymptotic behaviour of ∆ n is the same for Ex(C 2 ) as for Ex(C 2 -1 ). We have shown this is the case for = 2 and = 3.

3. We conjecture an upper bound of the form ∆ n ≤ c log n for the class Ex(H 1 , . . . , H k ), whenever the H i are 2-connected (see also the concluding remarks of [START_REF] Mcdiarmid | Random graphs from a minor-closed class[END_REF], where this question was also asked). Examples show that this is not true for arbitrary H (see the discussion below). Using analytic methods, this upper bound can be proved for so-called subcritical classes of graphs (see [START_REF] Drmota | Extremal parameters in sub-critical graph classes[END_REF]), which include outerplanar and series-parallel graphs.

4. Which are the possible orders of magnitude of ∆ n when forbidding a 2-connected graph? Assuming the truth of the conjecture in item 1, are there other possibilities besides log n and log n/ log (k+1) n?

5. Which are the possible orders of magnitude of ∆ n for arbitrary minor-closed classes of graphs? Besides those discussed above, examples show that it can be constant (forbidding a star) and it can be linear (forbidding two disjoint triangles). The last statement follows from [START_REF] Kurauskas | Random Graphs with Few Disjoint Cycles[END_REF], where it is shown that the class Ex(C 3 ∪ C 3 ) is asymptotically the same as the class of graphs G having a vertex v such that G -v is a forest.

6. Is it true that if H consists of a cycle and some chords, all of them incident to the same vertex, then ∆ n = o(log n) holds in Ex(H) w.h.p.? These are the 2-connected graphs that are a minor of some fan F n , so that the proof of the first part in Theorem 3 does not hold.

7. Prove an upper bound ∆ n ≤ c log n for series-parallel graphs without using the analysis of generating functions as in [START_REF] Drmota | The maximum degree of series-parallel graphs[END_REF]. More generally, prove such a bound for graphs of bounded tree-width (series-parallel graphs are those with tree-width at most two). For outerplanar graphs this is easy, but we decided to leave out the proof of this result.

  )) log n, which tends to infinity. Hence, |B n | = o(|G n |), and thus w.h.p. (1-) log n log log n ≤ ∆ n , and the result follows.

Figure 2 :

 2 Figure2: The graph S s,t,u,w with the notation as in Lemma 6, and with two optional edges (dashed)

  which tends to infinity by our choice of c. Hence, |B n | = o(|G n |), and thus w.h.p. ∆ n > (1 + ) log n log log n , and the result follows.

  log k log log log k , then the number of such blocks r 1 is at least k log log log k N log k. By the same arguments as before, the constructions of these blocks givea term r 1 log r 1 ≥ k log log log k N log k (log k + o(log k)) = k N log log log k(1 + o(

( 1 +

 1 o(1))(1 -c) z log z r j = (1 + o(1))(1 -c) (z log log log n) = (1 + o(1))(1 -c) C log n 8N ,

( 1 +

 1 o(1))(1 -c) k 8N log k 8N z = (1 + o(1))(1 -c) k 8N log log log log n = (1 + o(1))(1 -c) C log n 8N ,which for our choice of c and C large enough again is bigger than log n. Hence, in all cases, C(n)/R(n) → ∞, as desired, and the proof is finished.

  . If all the H i are 2-connected and none of them is a minor of a fan graph F n , then∆ n ≥ c log n w.h.p.This holds in particular if the H i are 3-connected or not outerplanar.2. If all the H i are 2-connected and contain C 4 as a minor (that is, all the H i are not C 3 ), then for every If all the H i are 2-connected and contain C 2 +1 as a minor for some ≥ 3, then

	3. If all the H i are 2-connected and contain C 5 as a minor, then for every > 0,
	∆ n ≥ (1 -)	log n log log log n	w.h.p.
	∆ n ≥ c	log n log ( +1) n	w.h.p.
		1
	log(2/α) > 0,
	∆ n ≥ (2 -)	log n log log n	w.h.p.

4. For ≥ 3, let c = c( ) be a positive constant satisfying c < 1/ .

Note that if all the H i are 2-connected, since every 2-connected graph contains C 3 as a minor, the bound ∆ n ≥ c log n/ log log n always holds for c < 1.

Proof. Throughout the proof we will assume for contradiction that there is some constant µ > 0 such that for each item and its corresponding graphs in B n , we have

|B n | ≥ µ|G n | infinitely often. Our goal is to show that we can obtain ω(|B n |) new graphs in G n , or equivalently, C(n)/R(n) → ∞, contradicting |B n | ≥ µ|G n |. Since,

by assumption, |B n | ≥ µ|G n |, as before, by Lemma 1, the subclass B n ⊆ B n of graphs with at least αn pendant vertices satisfies |B n | = (1 + o(1))|B n |, and we will in all cases below consider a graph of B n , where the definition of B n , and thus of B n , changes from case to case. 1. Let G = Ex(H 1 , . . . , H k ) and let B n ⊆ G n the graphs with ∆ n < c log n, where c is a positive constant satisfying c < 1 log(2/α) , and let h

  As before, assume that the H i contain C 2 +1 as a minor, and let G = Ex(H 1 , . . . , H k ). Let B n ⊆ G n be the graphs with ∆ n < c log n/ log ( +1) n (where c is a small enough constant), and let s = c log n/ log ( +1) n .

	For the choices	s = (1 -)	log n log log log n	,		r =	2 log s log log s
	and s to be the largest integer smaller or equal to s with the property of being divisible by r (note that
	s = (1 + o(1))s ), we can safely ignore the term (s + 1) log(α/2) + log(1/2) + (s/r) log r. Plugging in these
	values of s and r into the remaining term, we obtain
		(1 + o(1)) log n -s log r -	s r	log	s r
		≥(1 + o(1)) log n -s(log log s -log log log s) -	2	s log log s
		≥(1 + o(1)) log n -1 +	2		s log log s
		≥(1 + o(1)) log n -1 +	2		(1 -) log n ,
	which tends to infinity, since (1 + 2 )(1 -) < 1.
	4.
		)) (s + 1) log	α 2	+ log	1 2	+ log n +	s r	log r -s log r -	s r	log	s r	.

  and t = |B|. With this notation, it can be checked that G is either H 2,s,t or is in H * 2,s,t , possibly with v 3 or v 4 playing the role of v.

  1. blocks contributing to deg(v) at most log k log log k . That is, these are blocks whose root degree is at most Let r i be the number of blocks of class i and denote by k i the total contribution of edges belonging to a block of class i to deg(v). Clearly, k = k 1 + k 2 + k 3 , and also observe that r 1 ≥ k1 log log k

	log k log log k .
	2. blocks of type K 2,t with t > log k log log k
	3. blocks of type K + 2,t with t > log k log log k
	log k

  be a graph in B n and let v be a vertex of G such that for some constant C large enough, and since G ∈ B n , there are at least 2αn/3 pendant vertices not incident to v. We partition the blocks attached to v into different classes (see Lemma 5):1. blocks contributing to deg(v) at most log k log log k .

	k = deg(v) >	C log n log log log n

2. blocks of type K 2,s and K + 2,s with s > log k log log k . 3. blocks of type H 2,s,t or H * 2,s,t . 4. blocks of type H 2,s,t or H * 2,s,t (see the remark after Lemma 5).

  Proof. Let G = Ex(C 7 ). The proof starts as for Ex(C 5 ) and Ex(C 6 ). Let B n ⊆ G n the graphs with ∆ n > C log n/ log log log log n.We assume once more for contradiction that there is some constant µ such that |B n | ≥ µ|G n | infinitely often. As in the previous proofs, let B n ⊆ B n be the class of graphs that has at least αn pendant vertices, and which is such that every vertex is adjacent to at most 2 log n/ log log n pendant vertices. Again,|B n | = (1+o(1))|B n |.Let G be a graph in B n and let v be a vertex of G such that for some constant C large enough, and since G ∈ B n , there are at least 2αn/3 pendant vertices not incident to v. As before, we partition the blocks attached to v into different classes. Using Lemma 6, whose notation is used in the following (see also the remark following Lemma 6), we may partition them into

		n ≤ C	log n log log log log n	.
	k = deg(v) >	C log n log log log log n
	1. blocks contributing to deg(v) at most	log k log log log k
	2. blocks of type K 2,s , K + 2,s , H 2,s,t , H * 2,s,t , H 2,s,t and H * 2,s,t
	3. blocks of type S s,t,u,w , V s,t,E , and the corresponding graphs S * s,t,u,w , V * s,t,E
	4. blocks of type S s,t,u,w , V s,t,E , and the corresponding graphs S * s,t,u,w , V * s,t,E