7
$\begingroup$

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?

$\endgroup$
6
+50
$\begingroup$

I have often heard a graph property called hereditary when the property is closed under taking arbitrary induced subgraphs. However, this is somewhat stronger than the property you seem to be looking for: in a hereditary graph class, you can delete any vertex (or any subset of vertices) and get another graph with the desired property, while you just want there to be some vertex whose deletion yields a graph with the desired property. In particular, the property of being a tree is not hereditary, but the property of being a forest (disjoint union of trees) is hereditary, and it's possible to use this fact to prove that forests are 2-colorable in the same way you outlined in your question.

$\endgroup$
4
  • $\begingroup$ Thanks! That's a nice connection to make and if I end up making up a name of these graph properties maybe I'll call them "weakly hereditary" or something. But it'd be better to find out that someone else has already made up a name and then gone on to say lots of clever things about such graph properties. $\endgroup$ Apr 17 '17 at 13:54
  • 1
    $\begingroup$ Another property that's close to what you want is the concept of an "elimination ordering". Chordal graphs are characterized by having a simplicial elimination ordering: an ordering v_1, ..., v_n such that, when we delete the vertices in the specified order, each vertex has a clique for its neighborhood when it is deleted. People have also looked at other kinds of "elimination orderings", but I've usually seen them defined in terms of the neighborhood of $v$ when $v$ is deleted, not in terms of the overall structure of the graph when $v$ is deleted. $\endgroup$ Apr 17 '17 at 14:10
  • $\begingroup$ see, for example: dx.doi.org/10.1016/j.disc.2014.12.014 $\endgroup$ Apr 17 '17 at 14:10
  • $\begingroup$ Well, I was hoping to find more specific references, but it looks like nobody knows anything more than you do. Thanks again! $\endgroup$ Apr 27 '17 at 22:37
5
$\begingroup$

There is a class of stronger properties than you ask for, however it is applicable to your example. This class is called connected-hereditary properties, i. e. graph properties that are closed with respect to connected induced subgraphs. Particularly, being a tree is a connected-hereditary property.

$\endgroup$
1
  • $\begingroup$ Thank you; I guess this is the most general term so far. A couple of natural examples of "growable" properties that show it's still too specific: being an Apollonian network; having average degree less than $k$ for any fixed $k$. $\endgroup$ Apr 21 '17 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.