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

- 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.

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

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

Assume first that

So we may assume that there exist

Thus we may assume that x and y can be chosen so that neither is universal. As

Graph 1 of order 9:

We may assume that (

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)).

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.