Induction Through Edge Contraction

Why Contract an Edge?

Induction on a graph often works by reducing its number of vertices or edges, proving a statement for the smaller graph, and then translating the result back. Edge contraction is a vertex-reducing operation: it combines two adjacent vertices into one. It is useful only when the induction hypothesis applies to the graph produced and when the result for that graph can be transferred back. Both checks matter. Contraction preserves connectedness, for example, but it does not preserve every graph class.

All graphs in this tutorial are finite and simple. A graph is connected if every pair of its vertices can be joined by a path. A tree is a connected graph with no cycle. A spanning tree of $G$ is a subgraph that is a tree and has vertex set $V(G)$.

Definition: Let $uv$ be an edge of a simple graph $G$. To contract $uv$, identify $u$ and $v$ as one new vertex $x$, remove the edge $uv$, and replace each edge from $u$ or $v$ to a third vertex by an edge from $x$ to that vertex. If both $u$ and $v$ were adjacent to the same third vertex, retain just one of the resulting edges. The graph obtained is denoted $G/uv$. This convention removes loops and merges parallel edges, so $G/uv$ is again simple.

Because exactly two vertices become one, contraction always reduces the order by one. The size can drop by more than one: edges from $u$ and $v$ to a common neighbor become a single edge. Write $N(u)$ for the vertices adjacent to $u$, and let $c=|N(u)\cap N(v)|$. Since $uv$ is an edge in a simple graph, $u$ is not in $N(u)$ and $v$ is not in $N(v)$; the common neighbors counted by $c$ are third vertices.

Counting rule: If $G$ is simple and $uv\in E(G)$, then $$ |V(G/uv)|=|V(G)|-1,\qquad |E(G/uv)|=|E(G)|-1-c, $$ where $c=|N(u)\cap N(v)|$.

The edge $uv$ disappears, accounting for one lost edge. For each common neighbor $w$, the two edges $uw$ and $vw$ become one edge $xw$, accounting for one further loss. Every other edge remains represented by exactly one edge after contraction. This gives the size formula.

Worked Example: Counting the Edges After Contraction

Let $G$ have vertex set $V=\{1,2,3,4,5\}$ and edge set $E=\{12,23,13,34,45,51,35\}$. Contract the edge $13$, and compute the order and size of the resulting graph.

Let $x$ be the vertex formed by identifying $1$ and $3$. The neighbors of $1$ other than $3$ are $2$ and $5$; the neighbors of $3$ other than $1$ are $2,4,5$. Thus $N(1)\cap N(3)=\{2,5\}$, so $c=2$. The original graph has $5$ vertices and $7$ edges. The formula gives $|V(G/13)|=5-1=4$ and $|E(G/13)|=7-1-2=4$.

Listing the edges confirms the count. Edges $12$ and $23$ become the single edge $x2$; edge $34$ becomes $x4$; edges $51$ and $35$ become the single edge $x5$; and $45$ remains. Therefore $V(G/13)=\{x,2,4,5\}$ and $E(G/13)=\{x2,x4,x5,45\}$.

Check: The listed contracted graph has four vertices and four distinct edges, agreeing with both computed values. The two merged pairs are precisely the pairs of edges to common neighbors $2$ and $5$.

What Contraction Preserves

Proposition: If $G$ is a connected simple graph and $uv\in E(G)$, then $G/uv$ is connected.

Proof. Let $x$ be the vertex formed by identifying $u$ and $v$. Take any two vertices $a,b$ of $G/uv$. Regard $a$ and $b$ as vertices of $G$, except that $x$ may be represented by either $u$ or $v$. Since $G$ is connected, there is a path in $G$ between the chosen representatives. Replace every occurrence of $u$ or $v$ on that path by $x$. Edges on the path either remain edges after contraction or become the same edge when parallel edges are merged; the contracted edge $uv$, if used, becomes a repeated vertex $x$ and can be omitted. The resulting sequence gives a walk from $a$ to $b$ in $G/uv$, and deleting any repeated sections yields a path. Thus every pair of vertices in $G/uv$ is joined by a path, so it is connected. $\square$

This proposition supplies an important hypothesis check for induction: contracting an edge of a connected graph produces a smaller connected simple graph. It does not say that contraction preserves every property of the original graph. When a proof uses an induction hypothesis restricted to a particular class, verify separately that the contracted graph is still in that class.

Worked Example: Contraction Can Leave a Graph Class

Let $G$ have vertex set $V=\{1,2,3,4\}$ and edge set $E=\{12,23,34,41\}$, a cycle of length four. Contract edge $12$ to a new vertex $x$.

The remaining vertices are $\{x,3,4\}$. Edge $23$ becomes $x3$, edge $34$ remains $34$, and edge $41$ becomes $4x$. Hence $G/12$ has edge set $\{x3,34,4x\}$, which is a triangle.

The original cycle is bipartite, with parts $\{1,3\}$ and $\{2,4\}$, because every listed edge joins different parts. The contracted triangle is not bipartite: along a triangle, assigning two colors while requiring the endpoints of every edge to differ forces the first and last vertices to have both the same and different colors. Therefore contraction does not preserve bipartiteness.

Check: The contraction reduces the order from $4$ to $3$. Vertices $1$ and $2$ have the common neighbor set $\varnothing$, so the size rule gives $4-1-0=3$ edges, exactly the three edges listed for the triangle.

A Contraction Induction Theorem

A natural property to prove by contraction is the existence of a spanning tree. The key transfer step is to take a spanning tree of the contracted graph and replace its contracted vertex with the original adjacent pair. The original edge joining that pair reconnects the two vertices.

Theorem: Every nonempty finite connected simple graph has a spanning tree.

Proof. We use induction on the number $n=|V(G)|$ of vertices, with the statement applying to every connected simple graph of that order.

If $n=1$, the graph with its single vertex and no edges is connected and has no cycle. It is itself a spanning tree.

Now let $n\ge2$, and assume the statement holds for every nonempty connected simple graph with fewer than $n$ vertices. A connected graph with at least two vertices has an edge: choose two distinct vertices and a path joining them; that path contains an edge. Choose $uv\in E(G)$, and form $H=G/uv$. By the contraction proposition, $H$ is connected; it is simple by the definition of contraction and has $n-1$ vertices. The induction hypothesis gives a spanning tree $T$ of $H$.

We construct a subgraph of $G$. Replace the contracted vertex $x$ in $T$ by $u$ and $v$. Keep every edge of $T$ not incident to $x$. For each edge $xy$ of $T$, choose one original edge between $y$ and one of $u,v$ that produced $xy$, and keep that original edge. Such an edge exists by the definition of contraction. Finally, include $uv$.

To verify that the resulting subgraph $S$ is a spanning tree, consider the components of $T-x$. Each is a tree and is joined to $x$ by exactly one edge of $T$. There is at least one such edge for each component because $T$ is connected. There cannot be two such edges: the path within that component between their endpoints, together with the two edges to $x$, would form a cycle in $T$. In $S$, each component is therefore still attached by exactly one edge, now to either $u$ or $v$. All components are connected to the central pair $u,v$, and $uv$ joins that pair, so $S$ is connected. No cycle can lie within one component, since it is a subtree of $T$; and a cycle cannot pass through a component and leave it by a different attachment, since each component has only one attachment. The edge $uv$ alone cannot create a cycle. Thus $S$ has no cycle. The construction includes every vertex of $G$, so $S$ is a spanning tree of $G$. This proves the induction step and the theorem. $\square$

Worked Example: Lifting a Spanning Tree Back

Let $G$ have vertex set $V=\{a,b,c,d,e\}$ and edge set $E=\{ab,bc,cd,da,ac,de\}$. Contract edge $cd$ to $x$, and use a spanning tree of the contracted graph to build one in $G$.

The neighbors of $c$ other than $d$ are $a,b$, and the neighbors of $d$ other than $c$ are $a,e$. Their common neighbors are $\{a\}$, so $c=1$. Since the original graph has $6$ edges, the contracted graph has $6-1-1=4$ edges. Its vertex set is $\{a,b,x,e\}$, and its edges are $ab,bx,ax,xe$: edges $ac$ and $da$ merge into $ax$, while $bc$ becomes $bx$ and $de$ becomes $xe$.

Choose the three edges $ab,bx,xe$ for a spanning tree of the contracted graph. To lift this tree, represent $bx$ by the original edge $bc$, represent $xe$ by $de$, retain $ab$, and add the contracted edge $cd$. The selected original edges are $ab,bc,cd,de$, and their vertices form the path $a-b-c-d-e$.

Check: The path contains all five vertices, has four edges, and has no cycle, so it is a spanning tree. The contracted tree likewise contains all four contracted vertices and uses three edges.

Common Pitfalls and a Reliable Checklist

Assuming contraction removes only one edge. For the graph in the first worked example, a tempting but incorrect calculation is $|E(G/13)|=7-1=6$, on the assumption that only the contracted edge disappears. This misses the two pairs of edges that merge. The common neighbors are $2$ and $5$, since $12,23,15,$ and $35$ are present; hence $c=2$. The correct calculation is $|E(G/13)|=7-1-2=4$, matching the explicit edge list.

Forgetting the graph class in the induction hypothesis. A proof about connected graphs can use the induction hypothesis on $G/uv$ because connectedness is preserved. A proof whose induction hypothesis applies only to bipartite graphs cannot automatically do so: the four-cycle example contracts to a triangle, which is not bipartite.

Failing to explain the return step. A conclusion about the contracted graph is not yet a conclusion about the original graph. State how each edge of the smaller graph is represented before contraction, and explain what is added back. In the spanning-tree proof, the original edge $uv$ reconnects the two identified vertices, while each tree edge incident to $x$ is replaced by an original edge that produced it.

Before using contraction in an induction proof, check these points:

The chosen edge exists under the theorem's hypotheses.
The contracted graph has one fewer vertex and satisfies the induction hypothesis's graph-class requirements.
Loops and parallel edges are removed according to the stated convention.
The smaller graph's conclusion can be translated back, including any necessary restoration of the contracted edge.
Base cases are covered, including the one-vertex connected graph when the theorem permits it.

These checks separate the reduction itself from the proof that the desired structure survives the return step. In contraction induction, both are essential: the smaller graph must be eligible for induction, and its result must provide the right structure in the original graph.

Check Your Understanding

For each question, make explicit which edges survive, merge, or are restored.

If $uv$ has three common neighbors in a simple graph with $12$ edges, how many edges does the contracted graph have?
Give a reason that contracting an edge of a connected graph cannot disconnect the graph.
In the spanning-tree induction, why does each component of $T-x$ have exactly one edge to $x$?
Contract edge $12$ in the graph with vertex set $\{1,2,3,4\}$ and edge set $\{12,23,34,41,13\}$. List the resulting edges and explain whether the result is simple.
Why does contraction induction for a statement restricted to bipartite graphs require an additional argument beyond reducing the number of vertices?

Induction Through Edge Contraction

What You'll Learn