Can I Induct on Something Other Than n — Like the Number of Edges in a Graph?

When you first learn induction, the variable is always n — a positive integer. Sums, recursions, inequalities all live in the world of n \in \mathbb{N}. Then you open a discrete mathematics textbook and see a proof that starts "we induct on the number of edges in the graph" or "by induction on the height of the tree", and it feels like a rule has just been broken. Can you really do that?

Yes — and this flexibility is one of the most useful things about induction. The variable in an inductive proof does not have to be called n, and it does not have to refer to a count of generic objects. It just has to be a non-negative integer quantity that you can peel one unit off, ending up with a smaller instance of the same kind of problem.

The real requirement

Strip induction down to its logical skeleton. Induction works on any collection S of objects provided:

You can attach a non-negative integer size \sigma(x) to every object x \in S.
The set of objects of each size is finite (or at least well-ordered).
The statement P is something you can check on each object.

Then to prove "P holds for every x \in S" by induction on size, you prove:

Base case. P(x) holds for every object of minimum size.
Inductive step. For every object x with \sigma(x) = k+1, assume P holds on all objects of size \leq k, and deduce P(x).

The variable of induction is \sigma, not n. You are still inducting on a non-negative integer; you have just chosen a non-obvious quantity to call "the integer we are climbing."

Why this is still ordinary induction: once you fix \sigma, the statement "P holds for every object of size exactly k" is a claim indexed by k. Proving it by weak or strong induction on k is ordinary induction — with the extra bookkeeping that for each k, there may be many objects to check. The induction lives on the integers k; the objects are the things you are reasoning about, not the induction variable itself.

Inducting on edges: an example

Claim. Every finite connected graph on n \geq 1 vertices has at least n - 1 edges.

Induct on the number of edges e, not on the number of vertices.

Base case (e = 0). A graph with 0 edges is connected only if it has exactly one vertex (otherwise it has isolated vertices and is disconnected). One vertex satisfies 0 \geq 1 - 1 = 0. True.

Inductive step. Assume the claim holds for every connected graph with at most k edges. Take a connected graph G with k+1 edges and n vertices.

If G has a cycle, pick any edge on the cycle and remove it. The resulting graph G' has k edges, the same n vertices, and is still connected (removing a cycle edge never disconnects). By the hypothesis, G' has at least n - 1 edges, so k \geq n - 1, which gives k + 1 \geq n \geq n - 1. Done.
If G has no cycle, it is a tree. Pick a leaf (a vertex of degree 1) and remove it along with its edge. The resulting graph G' is connected with n - 1 vertices and k edges. By the hypothesis, k \geq (n-1) - 1 = n - 2, so k + 1 \geq n - 1. Done.

The induction variable here is e. The base case is e = 0. The inductive step peels off one edge and reduces to a smaller graph.

Inducting on tree height

Claim. A binary tree of height h has at most 2^{h+1} - 1 nodes.

Induct on the height h.

Base case (h = 0). A tree of height 0 has 1 node. Indeed 2^{0+1} - 1 = 1. True.

Inductive step. Assume the claim holds for every binary tree of height at most k. A tree of height k+1 consists of a root and up to two subtrees, each of height at most k. By the hypothesis, each subtree has at most 2^{k+1} - 1 nodes, so the total is at most 1 + 2(2^{k+1} - 1) = 2^{k+2} - 1, as required.

The induction variable is h. The subtree structure naturally reduces the height by at least one.

Inducting on game moves

Claim. In the game of Nim with n stones and a single pile, the player who starts loses if and only if n = 0.

Induct on n, the number of stones. (Here n is a natural choice; moves reduce the pile by at least 1, so each move takes you to a smaller instance of the same game.)

Games lend themselves to induction because a move produces a strictly smaller position — the "smaller" being measured by some non-negative quantity like pile size, number of pieces on the board, or moves remaining. The induction proceeds on that quantity.

Inducting on formula complexity

In logic, you often induct on the complexity of a formula — the number of logical connectives it contains, or the depth of its parse tree. To prove that every formula has a property (is equivalent to one in disjunctive normal form, can be evaluated in a certain way, etc.), you induct on complexity. Base case: atomic formulas have no connectives. Step: a formula with one more connective is built from simpler formulas to which the hypothesis applies.

The variable here is the connective count. Not n, but a non-negative integer all the same.

The warning: your "size" must actually decrease

The one place this flexibility breaks down is if your chosen quantity does not actually decrease when you take a step. If the operation you call "simplify" might leave the size the same or increase it, you do not have a legitimate induction — there is no guarantee the process terminates. This is the hidden requirement behind the well-ordering principle: a strictly decreasing sequence of non-negative integers is finite. Without strict decrease, you could circle forever.

Always check: after the operation that reduces to a smaller case, is the induction variable strictly smaller? If yes, the induction is valid. If no, you need a different quantity.

The broader picture

Induction is really a special case of structural induction — a technique where you prove a property of all objects in some inductively-defined set. For natural numbers, the inductive definition is "1, and whenever you have n, you have n+1." For trees, the inductive definition is "a leaf, or a node with children that are trees." For formulas, the inductive definition is "an atom, or a formula built from simpler formulas by applying a connective." In each case, induction climbs the structure.

The number n is just the simplest inductively-defined object. Once you understand that induction lives on any inductive structure, you see that the question "can I induct on edges?" is the same question as "can I induct on n?" — the answer is yes in both cases, and for the same reason.