Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.