In a paper on Hadwiger's conjecture, [https://web.math.princeton.edu/~pds/papers/hadwiger/paper.pdf](https://web.math.princeton.edu/%7Epds/papers/hadwiger/paper.pdf), Seymour explains various results on excluding the complete graph as a minor.


In particular, there is a nice bound on the number of edges, due to Mader, as follows:


If $t\leq 7$ and $n\geq t-2$ then every $K\_t$-minor free graph $G$ on $n$ vertices has
$$ |E(G)|\leq (t-2)n-\frac{(t-1)(t-2)}{2}.$$


(The obvious application to Hadwiger, as Seymour describes, is that this bound controls the average degree and hence gives low minimum degree to which you can use induction to get a colouring result.)


Sadly the pattern fails for $t\geq 8$. Jorgensen and then Song and Thomas describe the exceptions explicitly for $t=8$ and $t=9$ respectively but as far as I can see no larger $t$ is understood. To be more precise Jorgensen's result says that if there is no $K\_8$-minor and the displayed inequality fails then the exact number of edges is known and $G$ can be built from $K\_{2,2,2,2,2}$ in a simple way (by "pure 5-sums").


However, in general the average degree in a $K\_t$-minor free graph can be large - Kostochka, Thomason, ... - so the "exceptions" will get really bad for large $t$.


I'm interested in this from a slightly different perspective. Are explicit descriptions known (or potentially tractable) of $K\_t$-minor free graphs for general $t$ provided that $n$ is quite small relative to $t$?


So a desired result would be something like:


For any natural number $t$ and any $t-2\leq n \leq 2t$, every $K\_t$-minor free graph $G$ on $n$ vertices has
$$ |E(G)|\leq (t-2)n-\frac{(t-1)(t-2)}{2},$$
unless $G$ is ... some exceptions like those in Jorgensen/Song and Thomas ...


If this is somehow easy then replace the vertex bound of $2t$ with something bigger.



Are K_t-minor free graphs on small vertex sets understood?
There is no known straightforward answer, but pseudorandom graphs must come into the answer. See the paper by Myers and Thomason.


[In response to the comment below] Look at recent papers by Postle--Norine--Song, plus earlier work by Reed--Kawarabayashi, all on Hadwiger's Conjecture. You will see that the difficulty with K\_t-minor-free graphs often occurs when the number of vertices is small when compared to t. In particular, for a suitable choice of c a random graph with ct sqrt(log t) vertices has no K\_t minor. This says that small K\_t minor-free graphs are wild! Another important conjecture (of Seymour and Thomas) is that the above edge bound does hold for sufficiently large highly connected graphs. Here "sufficiently large" is essential, otherwise random graphs provide counterexample.


