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
- every vertex has degree at least 7,
- every edge is incident with a vertex of degree 7, and
- 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)).
Acknowledgments
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.