In this paper it is shown that any 4-connected graph that does not contain a minor isomorphic to the cube is a minor or the line graph of V-n for some n greater than or equal to 6 or a minor of one of five graphs. Moreover, there exists a unique 5-connected graph on at least 8 vertices with no cube minor and a unique 4-connected graph with a vertex of degree at least 8 with no cube minor. Further, it is shown that any graph with no cube minor is obtained from 4-connected such graphs by 0-, 1-, and 2-summing, and 3-summing over a specified triangles. (C) 2000 Academic Press. [References: 13]
展开▼