How could one prove the following? Find a finite set of 3-connected graphs from which all can be constructed iteratively by the following operation, or show that no such set can exist. The operation consists of adding a new vertex to the graph H constructed so far and joinig it by t least three edges to some subdivision of H. I think it might be K_4 and K_{3,3} but I'm not sure.
Constructing 3-connected graphs
3
$\begingroup$
graph-theory
1 Answers
5
Take a look at this web page which addresses the much more general issue of inductive constructions for families of graphs. http://vlado.fmf.uni-lj.si/vlado/projects/indcla.htm For planar 3-connected graphs Steinitz's Theorem, in one form, states that all such graph can be constructed from the graph of the tetrahedron (K4) by three kinds of "face splits." Planar 3-connected graphs are the edge-vertex graphs of convex 3-dimensional polyhedra.