Consider the following proof by induction:
Theorem. All trees are $2$-colorable.
Proof. We induct on $n$, the number of vertices in the tree. When $n=1$, we may give the only vertex any color we like.
Assume that all $n$-vertex trees are $2$-colorable. To prove this for $(n+1)$-vertex trees, take an $n$-vertex tree $T$, $2$-color it, and then add an $(n+1)^{\text{th}}$ vertex $v$ connected by an edge to any vertex of $T$. The resulting tree $T+v$ can be $2$-colored by giving $v$ the opposite color of the vertex we just connected it to.
By induction, the theorem holds for all $n$.
This is not a very good proof, but it can be made to work by clarifying an unstated assumption: any $(n+1$)-vertex tree can be obtained by adding on to an $n$-vertex tree. (I've seen a textbook call this the "Tree Growing Procedure", possibly only for the sake of the pun.)
The corresponding assumption is not true for all kinds of graphs, and assuming it's always true leads us to such classic mistakes as:
Theorem. All planar graphs are $4$-colorable.
Nonproof. It suffices to color all maximal (triangulated) planar graphs, because we can always add edges to a planar graph to triangulate it, and a proper coloring of the triangulation is also a proper coloring of the original graph.
We prove this by induction on $n$. For $n \le 4$, a $4$-coloring exists because we may give each vertex its own color.
Assume that all $n$-vertex planar triangulations are $4$-colorable. To prove this for $(n+1)$-vertex planar triangulations, take an $n$-vertex one and add another vertex to it, drawing all possible edges.
The new vertex was added to the middle of a (triangular) face, so it is connected to three vertices of that triangle. The $n$-vertex graph had a $4$-coloring by the inductive hypothesis, which we may extend to a coloring of the new graph by giving the new vertex a color different from any of the three colors use for those vertices.
By induction, the theorem holds for all $n$.
(I'm possibly not making the argument very convincing, because I know it's wrong - but variants of this mistake are very common among students first learning graph theory.)
My question: is there a word for the families of graphs (or of combinatorial objects in general; this issue isn't limited to graph theory) for which a "Growing Procedure" exists, and this type of argument works? Is there a theory of when "Growing Procedures" exist?
