Lemma 16. There is an absolute constant C_*>0 , for example C_*=10^4 , such that, for every integer t≥2 and every nonempty graph P with h(P)<t , d(P)≤C_*t(2t). Consequently, every graph P with h(P)<t satisfies ℓ(P)≤2C_*t(2t)+1.

Choose a nonempty minor R of P whose density d is as large as possible. If d<10^4 , the claimed density estimate holds with C_*=10^4 . We may therefore assume d≥10^4 . Put n=|V(R)| . The graph R has no isolated vertex, since deleting one would increase its positive density. Contracting an edge xy with c_ xy common neighbors loses exactly 1+c_ xy edges. The maximality of d gives dn-1-c_ xy n-1 ≤d, hence c_ xy ≥d-1. There is a vertex v of degree at most 2d . Therefore J=R[N_R(v)] has at most 2d vertices and minimum degree at least d-1 . We first record a bound for connected dominating sets in any connected graph C of order at most 2d and minimum degree at least d/2 . Take m=4(2d)+1 independent uniform samples from V(C) . A fixed vertex has a neighbor in each draw with probability at least 1/4 , so the probability that some vertex has no sampled neighbor is at most 2d(3/4)^m≤2d(-m/4)<1. Consequently, some choice of at most m sampled vertices dominates C . The diameter of C is at most 11 : along a shortest path, the open neighborhoods of the vertices at positions 0,3,6,… are pairwise disjoint, each has at least d/2 vertices, and the graph has at most 2d vertices. There are at most four such positions. Joining each sampled vertex to one fixed sampled vertex along a shortest path therefore gives a connected dominating set of size at most 11m≤66(2d) , which is at most M=100(2d). We have M≤101(2d) and d≥6M . For the latter inequality, x/(2x) is increasing for x≥10^4 , and 10^4>606(20000) . We now construct q=(d)/(3M) pairwise adjacent, disjoint connected sets. Start with J_0=J . At step i , choose a component C_i of J_i , take a connected dominating set B_i of C_i of size at most M , and put J_ i+1 =C_i-B_i . For every retained vertex, passing to a component deletes no neighbor. Its neighbors in the original graph J that have disappeared are therefore all in previously chosen bags. As long as at most qM≤d/3 bag vertices have been deleted, each retained vertex has degree at least d-1-qM≥d/2. In particular, each chosen component has at least d/2+1 vertices, whereas M≤d/6 ; its deletion of B_i leaves a nonempty graph. The construction consequently continues for all q steps. Every later bag lies inside C_i-B_i , so it has an edge to B_i by domination. The bags form a K_q model. Since d/(3M)≥2 , h(P)≥q≥(d)/(6M) ≥(d)/(606(2d)). The hypothesis h(P)<t implies d/(2d)<606t . The elementary inequality (2d)≤2√d for d≥1 first gives d<(1212t)^2 . Since 2·1212^2<2^ 22 and t≥2 , (2d)<222+2 t≤12(2t). It follows that d<7272t(2t) . Together with the case d<10^4 and the inequality d(P)≤d , this proves the density claim with C_*=10^4 . Every nonempty subgraph of P has average degree at most 2C_*t(2t) , and hence has a vertex of degree at most 2C_*t(2t) . Successively deleting such vertices and coloring in the reverse order proves the asserted list-coloring bound. The empty graph causes no exception.