Edge Induction Through Deletion

Why Induct on Edges?

In edge induction, the quantity that decreases is the number of edges. Choose an edge $e$, apply an induction hypothesis to $G-e$, and then restore $e$. The last step is the essential one: an edge can change degrees, connect components, or impose a new coloring constraint. A complete proof must account for that change rather than assume the property survives automatically.

All graphs in this tutorial are finite and simple. When deleting an edge, we keep the same vertex set, so isolated vertices remain present. The induction hypothesis will be stated for all graphs with fewer edges, regardless of their number of vertices. This allows it to apply to $G-e$ without changing the order of the graph.

Definition: A proof by edge induction proves a statement $P(G)$ by induction on $m=|E(G)|$. It establishes $P(G)$ for graphs with no edges, assumes $P(H)$ for every graph $H$ with fewer than $m$ edges, and proves $P(G)$ for a graph with $m$ edges by deleting an edge and then justifying the effect of restoring it.

The induction hypothesis applies to every smaller graph, not just to a particular deletion chosen in advance. That freedom is useful when the proof needs an edge with a special feature, such as an edge in a forest. It does not remove the need to show that deleting that edge produces a graph to which the hypothesis applies.

State the induction parameter.
Set $m=|E(G)|$, and say the claim is being proved for all graphs with $m$ edges.

Delete an edge.
Choose $e\in E(G)$. Then $G-e$ has the same vertices and $m-1$ edges, so the induction hypothesis applies.

Restore the edge.
Identify exactly what adding $e$ changes, and show why the claimed property still follows.

Tracking Degree Parity

For a vertex $v$, its degree $\deg(v)$ is the number of edges incident with it. A vertex has even or odd degree according to the parity of this integer. Deleting one edge changes the degrees of exactly two vertices, so this is a natural property to examine by edge induction.

Theorem: Every finite graph has an even number of vertices of odd degree.

Proof. We use induction on $m=|E(G)|$, for graphs of any finite order. If $m=0$, every vertex has degree $0$, so there are no odd-degree vertices and their number is even. Now suppose $m\ge1$, choose an edge $e=uv$, and assume the theorem holds for every graph with fewer than $m$ edges. In $G-e$, the number of odd-degree vertices is even by the induction hypothesis. Restoring $e$ increases the degrees of $u$ and $v$ by $1$ and changes no other degree. At each endpoint, this switches parity: an even degree becomes odd, and an odd degree becomes even. Thus the number of odd-degree vertices either increases by $2$, decreases by $2$, or stays the same, depending on the parities of $u$ and $v$ before the edge is restored. In every case it remains even. Therefore $G$ has an even number of odd-degree vertices. $\square$

Worked Example: Checking Odd-Degree Parity

Let $G$ have vertex set $\{a,b,c,d,e\}$ and edge set $\{ab,bc,ca,cd\}$. Verify the degree-parity conclusion by deleting and restoring $cd$.

In $G$, the degrees are $\deg(a)=2$, $\deg(b)=2$, $\deg(c)=3$, $\deg(d)=1$, and $\deg(e)=0$. The odd-degree vertices are $c,d$, so there are $2$.

Now delete $cd$. The remaining edges are $ab,bc,ca$. The degrees in $G-cd$ are $2,2,2,0,0$, respectively, so the number of odd-degree vertices is $0$. Restoring $cd$ changes only $\deg(c)$ from $2$ to $3$ and $\deg(d)$ from $0$ to $1$. The odd-degree count therefore rises from $0$ to $2$, as the proof allows.

Check: The degree sum is $2+2+3+1+0=8=2\cdot4$, where $4$ is the number of edges. The two odd degrees contribute an even number of odd-degree vertices, in agreement with the theorem.

Edge Induction for Forests

A cycle is a closed sequence of at least three edges whose vertices, apart from the repeated starting and ending vertex, are distinct. A forest is a graph with no cycles; its connected components include isolated vertices. Write $c(G)$ for the number of connected components of $G$, counting every isolated vertex as one component.

For a forest, deleting any edge separates one component into two. Here is why: if the endpoints of the deleted edge were still connected by a path after deletion, that path together with the edge would contain a cycle. Also, deleting one edge cannot split its original component into more than two components: every vertex in that component has a path to one of the edge’s endpoints that does not use the deleted edge, by considering a path to an endpoint and stopping before it first traverses the edge. Thus the component splits into exactly two.

Theorem: If $G$ is a finite forest, then $$ |E(G)|=|V(G)|-c(G). $$

Proof. We induct on $m=|E(G)|$, with the statement asserted for every finite forest, including those with isolated vertices. If $m=0$, every vertex is an isolated component, so $c(G)=|V(G)|$, and the formula gives $0=|V(G)|-|V(G)|$. Now let $m\ge1$, and assume the formula holds for every forest with fewer than $m$ edges. Choose an edge $e$ of $G$. The graph $G-e$ is still a forest, because deleting an edge cannot create a cycle. It has $m-1$ edges and the same number $n=|V(G)|$ of vertices. By the fact just established, deleting an edge of a forest increases the component count by one, so $c(G-e)=c(G)+1$. The induction hypothesis gives $m-1=n-c(G-e)=n-(c(G)+1)$. Adding $1$ to both sides yields $m=n-c(G)$, as required. $\square$

Worked Example: A Forest with Several Components

Let $G$ have vertex set $\{1,2,3,4,5,6\}$ and edge set $\{12,23,45\}$. This graph consists of a path on $\{1,2,3\}$, an edge on $\{4,5\}$, and the isolated vertex $6$. Each component has no cycle, so $G$ is a forest.

There are $n=6$ vertices and $m=3$ edges. The components are $\{1,2,3\}$, $\{4,5\}$, and $\{6\}$, so $c(G)=3$. The formula gives $n-c(G)=6-3=3=m$.

To see the induction step, delete edge $23$. The components become $\{1,2\}$, $\{3\}$, $\{4,5\}$, and $\{6\}$, so the component count rises from $3$ to $4$. The smaller forest has $2$ edges, and $6-4=2$. Restoring $23$ adds one edge and joins the two components containing $2$ and $3$, returning to $3$ edges and $3$ components.

Check: Directly summing the number of edges in the three components gives $2+1+0=3$, the same as the formula.

Restoring an Edge in a Coloring Argument

A proper vertex coloring assigns colors to the vertices so that the endpoints of every edge have different colors. Deleting an edge can only remove a restriction on a coloring. Restoring it may make the existing coloring improper, but a new color always resolves that problem. This gives a basic bound, not necessarily the best possible coloring bound.

Theorem: Every finite simple graph with $m$ edges has a proper vertex coloring using at most $m+1$ colors.

Proof. We induct on $m$, for graphs of any finite order. If $m=0$, then there are no adjacent vertices, so all vertices, if any, can receive one color. Now suppose $m\ge1$, and assume the claim holds for every graph with fewer than $m$ edges. Choose an edge $e=uv$. The graph $G-e$ has $m-1$ edges, so by induction it has a proper coloring using at most $(m-1)+1=m$ colors. Keep that coloring on all vertices. If $u$ and $v$ have different colors, it remains proper after $e$ is restored, and it uses at most $m\le m+1$ colors. If they have the same color, give $u$ a new color not used by any vertex in the coloring of $G-e$. This new color is different from the color of every neighbor of $u$, including $v$, so the coloring of $G$ is proper and uses at most $m+1$ colors. The claim follows. $\square$

Worked Example: Restoring an Edge and a Color

Let $G$ have vertex set $\{a,b,c,d\}$ and edge set $\{ab,bc,cd,da,ac\}$. It has $m=5$ edges. Delete $ac$, leaving the 4-cycle with edges $ab,bc,cd,da$.

Color $G-ac$ by assigning color 1 to $a,c$ and color 2 to $b,d$. Check the four remaining edges: $ab$ has colors $1,2$, $bc$ has $2,1$, $cd$ has $1,2$, and $da$ has $2,1$. So this is a proper coloring of the graph with the deleted edge.

When $ac$ is restored, its endpoints both have color 1, so that coloring is no longer proper. Give $a$ a third color. The colors are now $a:3$, $b:2$, $c:1$, $d:2$. The five edges have endpoint colors $3,2$; $2,1$; $1,2$; $2,3$; and $3,1$, respectively. Every edge has differently colored endpoints.

Check: The coloring uses $3$ colors, and the theorem’s bound is $m+1=5+1=6$. Thus the example satisfies the bound, though this particular graph needs fewer colors than the bound guarantees.

A Common Mistake and a Useful Check

A frequent error is to prove only that the statement holds for $G-e$, then claim it holds for $G$ without examining the restored edge. For example, in the coloring example, one might say: “The graph without $ac$ is properly colored with two colors, so $G$ is properly colored with two colors.” That conclusion is false: the displayed coloring assigns color 1 to both $a$ and $c$, and the restored edge $ac$ joins them. The correction is to check the new edge explicitly and, when necessary, modify the coloring. The induction proof does exactly this by assigning a fresh color if the endpoints conflict.

When setting up an edge-induction proof, check three points: the base case includes graphs with isolated vertices; deleting an edge leaves a graph in the class covered by the induction hypothesis; and restoring the edge is handled in every relevant case. The examples illustrate different restoration effects: endpoint degrees switch parity, a forest edge joins two components, and a coloring constraint may require one additional color.

Check Your Understanding

For each question, identify what changes when the deleted edge is restored.

In a graph with edges $12,23,34$, compute the degrees, delete $23$, and compare the numbers of odd-degree vertices before and after restoration.
A forest has $8$ vertices and $3$ components. How many edges does it have? Explain how deleting one of its edges changes the component count.
In a proper coloring of $G-e$, the endpoints of $e$ have different colors. What does this imply about restoring $e$?
Why does the edge-count formula for a forest include isolated vertices in $c(G)$? Give a forest with no edges and at least one vertex to support your explanation.
State the missing step in the incorrect argument: “$G-e$ has a proper coloring with two colors; therefore $G$ has a proper coloring with two colors.”