Z. Song and R. Thomas, The extremal function for K_9 minors

Published in J. Combin. Theory Ser. B 96 (2006), 240-252.

Lemma 3.7 of the paper was proven with the use of computers, and here we give the necessary details. We have found all graphs G on 9,10,11,12 and 13 vertices such that
  1. every vertex has degree at least 7,
  2. every edge is incident with a vertex of degree 7, and
  3. for every vertex v of G the graph G\v has no K_7 minor.
To do this we have used the package nauty, version 2.2, written by Brendan McKay. Our small program serves to weed out graphs that do not satisfy the above conditions; the file explains how to use it. There has been a bug fix on 7/2/2017; the old version is here. Here is the list of graphs satisfying the above conditions as generated by nauty, and here are pictures of those graphs.

Lemma 3.7 in the paper asserts that all graphs satisfying conditions (1) and (3) satisfy conditions (A) and (B) stated in the paper. First of all, there are only two graphs that satisfy (1) and (3) and not (2), namely K_{2,2,3,3} and the graph obtained from it by deleting an edge joining two vertices in the color classes of size two. In other words, the only graph in the list that is not edge-maximal is graph 2 of order 10; it is possible to add one or two independent edges with ends in the set {6,7,8,9}.

To see that condition (A) holds for graphs G satisfying (1) and (3) we may assume that G is not isomorphic to K_{1,2,2,2,2}. Let (a1,b1,a2,b2)=(0, 3,1,4) for graphs 1, 2, and 3 of order 10 and also for the two additional graphs mentioned in the previous paragraph, let (a1,b1,a2,b2)=(0,11,2,10) for graph 1 of order 13, and let (a1,b1,a2,b2)=(0, 9,1,8) for the rest of the graphs.

To prove that condition (B) holds for all those graphs G let the sets A and B be as stated in condition (B), and assume that (B2) does not hold. A vertex in a graph is universal if it is adjacent to every other vertex of the graph. Let M be the set of all vertices of G that are not universal.

Assume first that A is a subset of B. Then M is a subset of B because M is included in the union of A and B. We may assume that G is the second graph of order 10 or one of its two supergraphs mentioned above, for otherwise (B3) holds for any pair of nonadjacent vertices a,b of G. In particular, G has no vertex adjacent to every other vertex, and so B={0,1,...,9}. If A intersects both {0,1,2} and {3,4,5} in at most one element, then (since A has at least five elements) we may assume that 6,7,8 belong to A, and on letting (a,b)=(7,0) we deduce that (B1) holds (because G+(0,1)+(6,7)+(7,8)>K_8). Thus we may assume that 0 and 1 belong to A, and by letting (a,b)=(0,3) we deduce that (B1) holds (because G+(0,1)+(3,4)>K_8).

So we may assume that there exist x in A-B and y in B-A. We first dispose of the case when x and y cannot be chosen so that neither is universal. In that case we may assume that x is universal; that limits G to four graphs in the list. Note that each of them has a unique universal vertex. It follows that M is a subset of B, for otherwise a vertex in M-B can replace x, yielding a choice of (x,y), where neither is universal. Let u,v be nonadjacent vertices in A. Then G+(u,v) does not satisfy (3). (We said above that there is only one graph in our list which is not edge-maximal, and that graph has no universal vertex.) Thus for some w the graph G+(u,v)-w has a K_7 minor. If w is universal, then G+(u,v) has a K_8 minor, and we are done. Otherwise w belongs to M, and hence to B, and so graph obtained from G+(u,v) by adding all missing edges wb for b in B has a K_8 minor, as desired.

Thus we may assume that x and y can be chosen so that neither is universal. As A and B do not satisfy property (B2), it follows that for any a in N(x)-A, the vertices x and a have at least six common neighbors in G. This is rarely true for the graphs we are dealing with, and that is how, in the analysis below, it follows that a belongs to A. The argument that b is in B is analogous. Furthermore, if x and y are adjacent, then they have at least six common neighbors, and that eliminates many cases. Here are the choices for a and b to show that (B1) holds. We list, up to symmetry, all pairs (x,y) of nonadjacent vertices and all pairs (x,y) of adjacent vertices with at least six common neighbors such that neither is universal.

Graph 1 of order 9:
We may assume that (x,y)=(0,1). Let (a,b)=(2,4).

Graph 1 of order 10:
By symmetry we may assume that (x,y)=(0,1). Let (a,b)=(3,7) and note that G+(3,4)+(7,8)>K_8.

Graph 2 of order 10 and its two supergraphs:
If (x,y)=(0,1) let (a, b)=(3,6); if (x,y)=(6,7) or (x,y)=(6,8) let (a,b)=(0,3).

Graph 3 of order 10:
If (x,y)=(0,1) let (a, b)=(3,8); if (x,y)=(3,4) let (a,b)=(0,8); if (x,y)=(8,9) let (a, b)=(0,3).

Graph 4 of order 10:
We may assume that (x,y)=(0,1). Let (a, b)=(2,5).

Graph 5 of order 10:
If (x,y)=(0,1) let (a, b)=(3,7); if (x,y)=(7,8) let (a,b)=(0,2).

Graph 1 of order 11:
If (x,y)=(0,1) let (a, b)=(4,8); if (x,y)=(8,9) let (a,b)=(0,4).

Graph 2 of order 11:
If (x,y)=(0,1) or (x,y)=(0,3) let (a, b)=(4,8); if or (x,y)=(8,9) let (a,b)=(0,2).

Graph 3 of order 11:
We may assume that (x,y)=(0,1). Let (a, b)=(5,4).

Graph 4 of order 11:
We may assume that (x,y) is one of (0,1), (2,3), (3,4), (1,10), (8,3). Let (a,b)=(5,7). Notice that G+(5,4)+(7,6) and G+(5,6)+(7,8) both have K_8 minors.

Graph 1 of order 12:
We may assume that (x,y) is one of (1,0), (1,2), (1,11) . Let (a, b)=(7,9) and notice that G+(7,8)+(7,4)+(9,5) has a K_8 minor (contract the edges (0,4), (1,3), (2,10), and (6,8)).

Graph 1 of order 13:
We may assume that (x,y) is one of (4,3), (8,6), (8,3) . Let (a, b)=(0,1) and notice that G+(0,10)+(1,9) has a K_8 minor (contract the edges (0,11), (2,10), (3,6), (4,8), (4,5)).


We are indebted to Brendan McKay for providing us with the list of graphs on at most 13 vertices satisfying conditions (1) and (2) above. Having that list was extremely important; by checking for condition 3 and finding out that only 12 of those graphs satisfied it convinced us that we will be able to complete this project. Partial support by NSF and ONR is greatfully acknowledged.

This page was created on May 26, 2004.

This material is based upon work supported by the National Science Foundation under Grant No. 0200595. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.