Vertex Induction by Deletion and Reinsertion

The Deletion-and-Reinsertion Pattern

In vertex induction, the induction parameter is usually the order \(n=|V(G)|\). The basic move is to choose a vertex \(v\), remove it and every edge incident to it, and apply the induction hypothesis to the smaller graph. The final step is not automatic: one must show that the property under study survives when \(v\) and its incident edges are restored.

To prove a statement for all finite simple graphs by induction on order, start with order zero (or another carefully chosen base order). For the induction step, take a graph of order \(n\), select a vertex, apply the hypothesis to the graph of order \(n-1\), and then explain how to extend the conclusion. A useful proof-planning question is: what information about the removed vertex is needed to make that extension work?

The choice of vertex matters. For a statement about all graphs, an arbitrary vertex may be appropriate; for a statement about trees or forests, a leaf or an isolated vertex may be the useful choice. The induction hypothesis only concerns the smaller graph. It does not guarantee that the original graph has the desired property unless the reinsertion step is justified.

A First Inductive Bound

Proof. We use induction on \(n\), including \(n=0\). If \(n=0\), there are no vertices and hence no edges, and \(0=0(0-1)/2\). Suppose \(n\ge1\) and the claim holds for every simple graph of order \(n-1\). Choose any vertex \(v\). The graph \(G-v\) is simple and has order \(n-1\), so it has at most \((n-1)(n-2)/2\) edges by the induction hypothesis. Since \(G\) is simple, \(v\) has at most \(n-1\) neighbors, so \(\deg(v)\le n-1\). Restoring \(v\) adds exactly \(\deg(v)\) edges. Therefore \(|E(G)|=|E(G-v)|+\deg(v)\le (n-1)(n-2)/2+(n-1)=n(n-1)/2\). This argument includes disconnected graphs and graphs with isolated vertices; neither affects the bound on \(\deg(v)\). \(\square\)

Choosing a Vertex That Can Be Restored

For trees and forests, leaves provide a particularly useful deletion step. A forest is a graph with no cycles; a tree is a connected forest. A vertex of degree one is a leaf, while a vertex of degree zero is isolated.

Proof. If the forest has no edges, every vertex is isolated, so the claim holds. Otherwise, choose a component containing an edge and a path of maximum length in that component. Such a path exists because the graph is finite. Consider one endpoint \(x\). It has at least one neighbor, namely the next vertex on the path. If it had a neighbor outside the path, that neighbor could be added to extend the path, contradicting maximal length. If it had a neighbor on the path other than the next vertex, the segment of the path between those two vertices together with that extra edge would form a cycle, contradicting that the graph is a forest. Thus \(x\) has exactly one neighbor and is a leaf. \(\square\)

After deleting a leaf from a tree with at least two vertices, the remaining graph is still a tree. It has no cycle because it is a subgraph of a graph with no cycle. It is connected because a path between two remaining vertices cannot use a degree-one vertex as an internal vertex: an internal vertex of a path has two path-neighbors. Thus deleting a leaf gives a smaller tree, and restoring the leaf adds exactly one edge.

Proof. We use induction on \(n\). If \(n=1\), a simple graph on one vertex has no edges, so the number of edges is \(0=1-1\). Suppose \(n\ge2\) and the result holds for every tree of order \(n-1\). The lemma gives a leaf \(v\). As explained above, \(T-v\) is a tree of order \(n-1\). By the induction hypothesis it has \((n-1)-1=n-2\) edges. Restoring \(v\) adds exactly one edge because \(v\) is a leaf. Therefore \(T\) has \((n-2)+1=n-1\) edges. \(\square\)

Reinserting a Vertex in a Coloring Proof

The same pattern works when the property is not an edge count. A proper two-coloring assigns one of two colors to each vertex so that the endpoints of every edge have different colors. When a vertex is reinserted, its color must be checked against every neighbor, not just against one edge.

Proof. We induct on the number \(n\) of vertices. The empty forest has the empty coloring, which is proper because it has no edges. Let \(n\ge1\), and suppose the result holds for every forest of order \(n-1\). By the lemma, choose a vertex \(v\) of degree at most one. The graph \(F-v\) is a forest, since deleting vertices cannot create a cycle. By induction it has a proper two-coloring.

If \(v\) has one neighbor \(u\), assign \(v\) the color different from the color of \(u\). The only edge incident to \(v\) is \(uv\), so this assignment makes that edge properly colored, while all other edges were already properly colored in \(F-v\). If \(v\) is isolated, assign either color to it; there is no incident edge to check. In both cases the coloring extends to all of \(F\) and is proper. This covers the empty forest, isolated vertices, and components of every size. \(\square\)

Common Pitfalls and a Reliable Checklist

A frequent error is to assume that deleting one vertex removes one edge. It removes all edges incident to that vertex, whose number is \(\deg(v)\). For example, let \(G\) have vertex set \(\{c,1,2,3\}\) and edge set \(\{c1,c2,c3\}\). This is the star \(K_{1,3}\). Deleting \(c\) removes three edges, not one; \(G-c\) has zero edges. In general, the correct count is \(|E(G-v)|=|E(G)|-\deg(v)\).

Another mistake is to apply induction to a smaller graph and stop there. For the coloring proof, a coloring of \(F-v\) says nothing by itself about whether \(v\) can be colored. The proof succeeds because the chosen vertex has at most one neighbor: there is always a color available for one neighbor, and an isolated vertex has no restriction. If the chosen vertex had many neighbors, all its neighbors might already use both colors.

Before using vertex induction, check the following points:

• Is the induction parameter a nonnegative integer, and is the base case stated?
• Does deleting the chosen vertex leave a graph to which the induction hypothesis applies?
• Why is this vertex a suitable choice: arbitrary, a leaf, isolated, or something else?
• Which edges or constraints disappear on deletion, and exactly which return on reinsertion?
• Does the extension handle every possible case, including degree zero?

The method is a proof structure, not a guarantee that every graph statement is vertex-inductive. Its effectiveness depends on matching the vertex choice to the extension step. In edge counts, degree records precisely what deletion removes; in forests, a leaf ensures that reinsertion creates only one edge to check.