Common Pitfalls in Graph Induction

Four Questions to Ask of an Induction

Graph induction often works by deleting a vertex or edge, applying an induction hypothesis to the smaller graph, and then restoring what was removed. The outline is familiar, but it is not itself a proof. A deletion can leave the graph outside the class covered by the hypothesis; a chosen parameter may not decrease; or a claimed base case may omit a graph included in the theorem. A reduction can also destroy another assumption, such as a degree bound.

When checking an induction proof, make four checks explicit:

• Base case: Does it cover the smallest value allowed in the statement?
• Decrease: Does the reduction strictly lower the induction parameter?
• Applicability: Does the induction hypothesis concern graphs like the reduced graph?
• Preservation: Does the reduced graph still satisfy every assumption needed to use the hypothesis?

These checks are related but distinct. For instance, deleting an edge always decreases the number of edges, but the resulting graph may no longer be connected. Conversely, deleting an isolated vertex preserves the number of edges, so induction on the number of edges has not moved to a smaller case.

A Base Case That Must Not Be Skipped

Proof. We use induction on \(n\), with the theorem stated for every integer \(n\ge1\). If \(n=1\), the tree has one vertex and no edges: a loop is not allowed in a simple graph, and there is no second vertex to form an edge with. Thus \(|E(T)|=0=1-1\), proving the base case.

Now let \(n\ge2\), and assume the theorem holds for every tree on \(n-1\) vertices. A finite tree with at least two vertices has a leaf: take a path of maximum length, which exists because the graph is finite. At an endpoint \(v\), a neighbor other than the next vertex on the path cannot lie outside the path, since that would extend it. It cannot be an earlier vertex of the path, since that would create a cycle. Hence \(v\) has degree \(1\).

Delete \(v\) and its incident edge, obtaining \(T-v\). This graph has \(n-1\ge1\) vertices and is acyclic because deleting vertices cannot create a cycle. It is connected: for any two remaining vertices, a path between them in \(T\) cannot use the degree-\(1\) vertex \(v\) as an internal vertex, so that path remains in \(T-v\). Therefore \(T-v\) is a tree, and the induction hypothesis gives \(|E(T-v)|=(n-1)-1=n-2\). Restoring \(v\) restores exactly one edge, so \(|E(T)|=(n-2)+1=n-1\). This proves the result for \(n\) and completes the induction. \(\square\)

The base case matters because the theorem includes \(n=1\). Starting the induction step at \(n=2\), without separately checking \(n=1\), would leave the stated theorem unproved. One could instead state a different theorem restricted to \(n\ge2\), but that would not establish the result for all trees in the original range.

When the Reduction Does Not Decrease the Parameter

Induction on a nonnegative integer parameter requires every inductive step to reach a strictly smaller value of that parameter. Deleting a vertex does not necessarily decrease the number of edges: if the vertex is isolated, no edge is removed. This does not make vertex deletion invalid in every proof; it means that deletion cannot justify induction on edge count in that case.

When the Induction Hypothesis Does Not Apply

A proof must identify the exact class of graphs covered by its induction hypothesis. If the hypothesis says something about trees, for example, it cannot automatically be applied to a disconnected graph obtained by deleting a vertex from a tree. Deleting a leaf is useful in the tree proof above precisely because the remaining graph is still a tree; deleting an arbitrary vertex need not have that property.

A related failure occurs when the induction hypothesis is about a narrower class than the theorem’s conclusion requires. Before invoking it, write down the hypothesis in full, then verify that the reduced graph satisfies each part of it. “The graph is smaller” is not enough.

When a Reduction Breaks an Assumption

Even if a reduction decreases the parameter and produces a graph of the right general type, it may violate an additional hypothesis. Contraction illustrates this issue. Contracting an edge \(uv\) identifies \(u\) and \(v\) as one vertex; if the result is required to be simple, loops are removed and multiple edges are replaced by a single edge. A degree bound, however, need not be preserved.

A Repair: Do Not Delete an Arbitrary Edge from a Connected Graph

Here is a common invalid edge-induction step. Suppose the goal is to prove that every connected graph on \(n\ge1\) vertices has at least \(n-1\) edges. Deleting an arbitrary edge certainly reduces the edge count, but the resulting graph need not be connected. Consequently, an induction hypothesis stated only for connected graphs may not apply. The repair is to use a reduction that retains connectedness, or to prove the claim by a construction that does not need that deletion step.

Proof. If \(n=1\), then the graph has at least \(0=n-1\) edges. Now suppose \(n\ge2\), and fix a vertex \(r\). Begin with the reached set \(S=\{r\}\) and no selected edges. Whenever \(S\ne V(G)\), connectedness guarantees an edge with one endpoint in \(S\) and the other outside \(S\): take a path from \(r\) to any vertex outside \(S\), and consider the first edge of that path that leaves \(S\). Select that edge and add its outside endpoint to \(S\).

Each step adds exactly one new vertex and one edge. The process starts with one reached vertex and stops when all \(n\) vertices have been reached, so it takes exactly \(n-1\) steps. The selected edges are distinct: each selected edge has an endpoint that was outside \(S\) before its step, and both endpoints are in \(S\) afterward, whereas future selected edges must have an endpoint outside the then-current \(S\). Thus the graph contains at least these \(n-1\) distinct edges. \(\square\)

A Final Audit: Forests

Proof. Each connected component of a forest is a tree: it is connected by the definition of component and has no cycle because \(F\) has no cycle. Let the components have orders \(n_1,\ldots,n_c\). If \(F\) is empty, the sums below are empty sums equal to \(0\), and \(n-c=0-0=0\), so the formula holds. Otherwise, each \(n_i\ge1\), and the tree theorem gives \(n_i-1\) edges in component \(i\). Components have disjoint vertex and edge sets, so summing gives \(|E(F)|=\sum_{i=1}^{c}(n_i-1)=\sum_{i=1}^{c}n_i-c=n-c\). \(\square\)

This argument illustrates a useful audit habit: check the degenerate case before using a sum over components, and state why the theorem applies to every component. The tree theorem requires a tree with at least one vertex; each component in a nonempty forest meets that condition.

Common Mistakes to Catch

When reading or writing a graph-induction proof, watch for these specific warning signs:

• A base case is given for \(n=2\), but the theorem claims to cover \(n\ge1\). The one-vertex case still needs verification.
• A deletion is said to make the graph “smaller,” but the stated induction parameter is unchanged. For edge induction, deleting an isolated vertex does not reduce the edge count.
• The reduced graph has fewer vertices or edges, but no longer belongs to the class in the induction hypothesis. Deleting the center of \(K_{1,2}\) does not leave a tree.
• A reduction preserves the graph class but breaks an extra hypothesis. Contracting an edge in the displayed example changes the maximum degree from \(3\) to \(4\).
• The proof says “apply induction” without specifying what the smaller graph is, which hypothesis applies to it, and how the removed part is restored.