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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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. 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|cite|improve this answer

Your Answer


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