Choosing a Decreasing Graph Parameter

Why the Induction Parameter Matters

In a graph proof by induction, the parameter is the quantity that measures progress. A reduction may make the graph look simpler without making the chosen parameter smaller. It may also reduce the parameter while destroying a hypothesis that the argument needs, such as connectedness. A reliable choice therefore has two separate checks: the parameter must strictly decrease, and the reduced graph must remain suitable for the induction step.

Throughout, graphs are finite and simple. Write \(n(G)=|V(G)|\) for the order and \(m(G)=|E(G)|\) for the size. The order counts vertices; the size counts edges. For an edge \(e\), \(G-e\) is the graph with the same vertex set and with \(e\) removed. For a vertex \(v\), \(G-v\) removes \(v\) and every edge incident with \(v\). These operations are useful reductions, but they do not have the same effect on every parameter.

For a graph \(G\), common choices are \(n(G)\), \(m(G)\), or the ordered pair \((n(G),m(G))\). The pair is compared lexicographically: \((a,b)<_{\mathrm{lex}}(c,d)\) means either \(a<c\), or \(a=c\) and \(b<d\). Thus the first coordinate has priority. A drop in the first coordinate is enough, regardless of the second; if the first coordinate stays fixed, the second must drop.

The Induction Test

Proof. We use strong induction on the nonnegative integer \(\rho(G)\). At \(\rho(G)=0\), there cannot be a reduced graph in \(\mathcal C\) with smaller nonnegative parameter. The stated implication therefore gives \(P(G)\) in this base case. Now fix \(r>0\) and assume \(P(H)\) holds for every \(H\in\mathcal C\) with \(\rho(H)<r\). Let \(G\in\mathcal C\) have \(\rho(G)=r\). Every allowed reduction \(H\in\mathcal C\) has \(\rho(H)<r\), so the induction hypothesis gives \(P(H)\) for each such \(H\). The assumed implication then gives \(P(G)\). This proves the statement for each parameter value, and hence for all \(G\in\mathcal C\). \(\square\)

This criterion highlights a condition that can be missed: the reduction must produce a graph in \(\mathcal C\). A smaller graph outside the class cannot be handled by an induction hypothesis that only concerns members of \(\mathcal C\). Also, the implication in the theorem is a real proof obligation. Choosing a parameter does not itself show that \(P(G)\) follows from the reduced cases.

Proof. Suppose there were an infinite strictly decreasing sequence \((a_i,b_i)\). Its first coordinates never increase. They can decrease only finitely many times, because they are nonnegative integers. From some index onward the first coordinate must therefore be constant, say equal to \(a\). After that index, every strict lexicographic decrease must decrease the second coordinate. The second coordinates would then form an infinite strictly decreasing sequence of nonnegative integers, which is impossible. Thus no such sequence exists. \(\square\)

For induction, one can also order all possible pairs directly: for each fixed first coordinate, induct on the second, and use induction on the first coordinate to move to the next value. The fact above explains why a lexicographic parameter is a legitimate measure of progress, even when individual reductions change different coordinates.

Worked Example: Edge Count for Edge Removal

In general, deleting one edge reduces size by exactly one and leaves order unchanged. Consequently, size is a natural parameter when every reduction removes an edge and keeps the graph inside the class being studied. It is not automatically suitable if a step sometimes makes no edge removal, or if the reduced graph no longer satisfies a required condition.

Worked Example: Vertex Count and a Hypothesis That Fails

Deleting a vertex \(v\) always decreases order by one. It removes \(\deg(v)\) edges, so the new size is \(m(G-v)=m(G)-\deg(v)\), which is no greater than \(m(G)\). These calculations establish parameter changes; they do not establish that a chosen property, such as connectedness, survives. The proof must check that separately, or use a class broad enough to include the reduced graph.

Worked Example: A Lexicographic Pair for Mixed Reductions

This example shows why a pair can be convenient when the proof uses more than one kind of step: one step may keep the order fixed and lower the size, while another lowers the order. The lexicographic comparison checks each transition precisely. It is not enough to say that a graph “gets smaller”; write the old and new parameter values and identify the coordinate that decreases.

A Practical Choice of Parameter

Before beginning an induction, make a short reduction audit. State the allowed operation, compute its effect on each candidate parameter, and check the hypotheses for the smaller graph. The following table summarizes the basic calculations.

The table gives parameter arithmetic, not a universal permission to use each operation. For example, if a proof concerns connected graphs and its reduction creates a disconnected graph, the induction hypothesis does not apply. Possible responses include finding a different reduction, enlarging the induction class and proving the statement for that class, or proving an additional fact that justifies the step. Which response works depends on the statement being proved.

Keep the base cases aligned with the parameter as well. Induction on size reaches graphs of size zero, which may still have many vertices. Induction on order reaches graphs with no vertices, but such a base case may not belong to a restricted class such as connected graphs. With a lexicographic pair, both coordinates and the allowed base objects need to be understood. The measure organizes the proof; it does not decide what the base cases mean.

Common Pitfall: Decrease Is Not Enough

A common incorrect argument is: “Delete a vertex; the graph has fewer vertices, so induction applies.” For the graph in the second worked example, deleting \(b\) does give \(n(G-b)=2<3=n(G)\). But if the induction statement is only for connected graphs, the reduced graph has two isolated vertices and is outside the induction class. The corrected reasoning is: “The order decreases, and the reduced graph is still a finite simple graph. Therefore induction applies if the statement is being proved for all finite simple graphs; it does not apply under a connected-graph-only hypothesis unless that hypothesis is otherwise handled.”

The same distinction applies to edge count and lexicographic pairs. Always verify both parts of the induction step: strict decrease of the chosen parameter and legitimate use of the induction hypothesis. A parameter is a measure of progress, not a substitute for checking the proof's assumptions.