Hereditary Properties in Minimal-Counterexample Proofs

Why Inheritance Matters

A minimal-counterexample proof reduces a graph and then applies the minimality assumption to the smaller graph. The crucial question is whether the reduced graph still satisfies the hypotheses of the statement being proved. A property that is preserved by the chosen deletion makes this step legitimate; a property that is not preserved can make the whole reduction invalid.

Here graphs are finite and simple. A graph property is a condition that a graph may or may not satisfy. For example, being 3-colorable is a property: a graph is 3-colorable if its vertices can be assigned at most three colors so that the endpoints of every edge receive different colors. A subgraph \(H\) of \(G\) has \(V(H)\subseteq V(G)\), and every edge of \(H\) is an edge of \(G\) whose two endpoints lie in \(V(H)\). It may omit some such edges. An induced subgraph on \(S\subseteq V(G)\), denoted \(G[S]\), includes every edge of \(G\) with both endpoints in \(S\).

When a graph has no vertices, it is the empty graph. For properties such as colorability, the empty graph satisfies the property: its empty coloring is proper. Stating what happens in this case avoids an exception when a sequence of deletions removes every vertex.

A Deletion Test for Heredity

Proof. Suppose first that the property is subgraph-hereditary. For any vertex \(v\), the graph \(G-v\) is a subgraph of \(G\), so it has the property whenever \(G\) does. For any edge \(e\), \(G-e\) is also a subgraph of \(G\), and therefore has the property as well.

Conversely, suppose the property is preserved under both kinds of single deletion, and let \(H\) be any subgraph of a graph \(G\) with the property. Delete from \(G\) every vertex not in \(V(H)\), one at a time. Each deletion preserves the property by assumption. The resulting graph has vertex set \(V(H)\), and its edge set consists of all edges of \(G\) with both endpoints in \(V(H)\). Now delete each of these edges that is not in \(E(H)\), again one at a time. Each edge deletion preserves the property. What remains is exactly \(H\), so \(H\) has the property. If no vertices or no edges need deleting at a stage, that stage changes nothing. Thus the argument also covers \(H=G\) and the empty graph. \(\square\)

This test identifies which reductions are available. Preserving a property under vertex deletion alone establishes induced-subgraph-heredity, not necessarily subgraph-heredity. Conversely, if a proof deletes only edges, it is enough to know that the hypothesis is preserved under edge deletion; a stronger general claim is not needed.

Using Heredity in a Minimal-Counterexample Proof

Suppose a theorem is meant to apply to every graph satisfying a hypothesis \(P\). A counterexample is a graph satisfying \(P\) but not the claimed conclusion. If at least one counterexample exists, finiteness allows us to choose one with the fewest vertices. A reduction is useful only if the smaller graph still satisfies \(P\); heredity can guarantee this. Minimality then says that the reduced graph is not a counterexample, so it has the desired conclusion. A separate extension argument must show that this conclusion can be transferred back to the original graph.

Proof. Let \(G\) be a counterexample with the fewest vertices, and let \(H\) be a smaller graph obtained by a deletion that preserves \(P\). Since \(P(G)\) holds and the deletion preserves \(P\), \(P(H)\) holds. If \(T(H)\) failed, then \(H\) would be a counterexample with fewer vertices than \(G\), contradicting the choice of \(G\). Therefore \(T(H)\) holds. This conclusion alone does not imply \(T(G)\); the proof must supply an extension or reconstruction argument. \(\square\)

The principle is deliberately conditional. It does not say that every deletion preserves every hypothesis, or that a valid conclusion for the reduced graph automatically extends. The reduction must satisfy both obligations: preserve the hypotheses and support a correct extension step.

Worked Application: 2-Degenerate Graphs

Proof. Suppose the theorem is false, and choose a 2-degenerate graph \(G\) that is not 3-colorable and has the fewest vertices among all such graphs. The empty graph is 3-colorable, so \(G\) is nonempty. Since \(G\) itself is a nonempty subgraph of \(G\), the definition of 2-degeneracy supplies a vertex \(v\) with degree in \(G\) at most \(2\).

The graph \(G-v\) is still 2-degenerate. Indeed, each nonempty subgraph of \(G-v\) is also a subgraph of \(G\), so it has a vertex of degree at most \(2\) within that subgraph. Also, \(G-v\) has fewer vertices than \(G\). By the minimal choice of \(G\), \(G-v\) must be 3-colorable; otherwise it would be a smaller 2-degenerate graph that is not 3-colorable.

Take a proper coloring of \(G-v\) using colors \(A,B,C\). Vertex \(v\) has at most two neighbors in \(G\), so those neighbors use at most two of the three colors. At least one color among \(A,B,C\) is therefore absent from the neighbors of \(v\). Assign that color to \(v\). Every edge not incident with \(v\) remains properly colored because its endpoints were already properly colored in \(G-v\); every edge incident with \(v\) has endpoints of different colors by the choice of color. This gives a proper 3-coloring of \(G\), contradicting the assumption that \(G\) is not 3-colorable. Hence every finite 2-degenerate graph is 3-colorable. \(\square\)

The proof uses heredity of the hypothesis in a specific way: 2-degeneracy survives vertex deletion, so minimality applies to \(G-v\). It also checks the separate extension step: a vertex with at most two neighbors can be assigned one of three colors not used by those neighbors. Neither step can be omitted.

Common Pitfalls

Testing one graph is not proving a property is hereditary. Showing that one particular subgraph of one particular 3-colorable graph is 3-colorable is only an example. The general proof must begin with an arbitrary graph having the property and an arbitrary subgraph, then explain why the property survives for that choice. For colorability, restriction of the coloring works because every retained edge was already present.

Do not confuse induced-subgraph-heredity with subgraph-heredity. Vertex deletion produces an induced subgraph, but arbitrary subgraphs may also omit edges. A property preserved under vertex deletion need not be preserved under edge deletion. The deletion test requires both kinds of preservation to conclude subgraph-heredity.

Do not use minimality before checking the hypothesis. If the reduced graph no longer satisfies the theorem's hypothesis, it is not a smaller counterexample in the relevant class, and minimality says nothing about it. Connectedness, for example, can fail after deleting a vertex or edge. State why the particular property survives the particular reduction.

Do not stop after obtaining a smaller graph with the conclusion. A coloring of \(G-v\), for instance, is not yet a coloring of \(G\). The proof must explain how to restore \(v\) without violating any edge condition. In the 2-degenerate application, the degree bound supplies the needed unused color.