Induction on Graphs: Reducible Configurations

Note: While this post does not assume any familiarity with algorithms or graph theory, this would perhaps make the post easier to understand.

There are many videos on the Internet about the $4$ -Color Theorem, and the use of “reducible configurations” in its proof. But what exactly are reducible configurations, and how do they work? It turns out that they are simply a generalized form of induction.

Many theorems about natural numbers are proven using a technique called induction. Let’s say we want to prove something simple, like the following:

Theorem 0: Every natural number $n$ can be written as $2k$ or $2k + 1$ for some integer $k$ (equivalently, $n$ is either even or odd).

To prove this theorem by induction, we make two observations, often called the base case and inductive hypothesis:

Base Case: The theorem holds for $n = 1$ , because $1$ is odd: $1 = 2(0) + 1$ .

Inductive Hypothesis: If $n$ is a natural number and is even or odd, then $n + 1$ is even or odd.

Proof of the inductive hypothesis: Suppose $n$ is even or odd. If $n$ is even, then $n = 2k$ for some integer $k$ . Then $n + 1 = 2k + 1$ , showing that $n + 1$ is odd. If $n$ is odd, then $n = 2j + 1$ for some integer $j$ . Then $n + 1 = 2j + 2 = 2(j + 1)$ , showing that $n + 1$ is even. In either case, $n + 1$ is even or odd.

It makes intuitive sense why the base case and inductive hypothesis imply that every natural number is even or odd: take the set of natural numbers, and we’ll keep track of the ones we’ve verified are either even or odd. We’ll color numbers we’ve verified blue. The base case allows us to color $1$ blue, since the base case says that $1$ is odd.

The inductive hypothesis says that anytime a particular number $n$ is even or odd, $n + 1$ is also even or odd. The inductive hypothesis, applied to the number $1$ , tells us we can color $2$ blue.

Applied to the number $2$ , the inductive hypothesis says we can color $3$ blue.

So, by mere repetition, we obtain the desired conclusion: for any natural number $n$ , we will eventually verify that n is even or odd.

Some of you are not convinced. Here’s a more formal argument: suppose for contradiction that there are natural numbers neither even nor odd. From the set of natural numbers that are not even or odd, pick the smallest one $n_0$ (which we can do since the natural numbers are well-ordered). Then $n_0 > 1$ , because of the base case. Thus $n_0 - 1 > 0$ is a natural number, and since there is no smaller counterexample than $n_0$ , we know that $n_0 - 1$ is even or odd. Thus by the inductive hypothesis, $n_0 - 1 + 1 = n_0$ is even or odd, contradicting the choice of $n_0$ as a counterexample to the theorem.

If this proof technique is new to you, I suggest reading more about it or practicing some problems which require induction for the sake of developing intuition. Now we’ll move on to inductive proofs on undirected graphs.

An undirected graph is a bunch of dots, with lines between some of the pairs of dots. (More formally: an undirected graph $G$ is a set of vertices $V(G)$ , together with a subset of the set of unordered pairs of vertices, denoted $E(G)$ ).

We can use induction to prove theorems about graphs. This is best illustrated through examples, of which I’ll be presenting three. Our first example will use the concept of a tree. A tree is a connected, undirected graph with no cycles.

Theorem 1: If $T$ is a tree, then $|E(T)| = |V(T)| - 1$ .

Proof: We use the fact that every tree has a leaf (a leaf is a vertex with only one edge coming out of it). This implies that every tree can be built up by starting from a single vertex and repeatedly adding leaves (adding a leaf involves adding both a vertex and an edge). I’ll leave it to the reader to verify these two assertions, but the picture beneath them should help:

1. Every tree has a leaf.

2. (1) implies every tree can be constructed by starting from the single-vertex-tree and repeatedly adding leaves.

With (1) and (2) in our arsenal, we can prove Theorem 1 by induction. We’ll first verify that the following two claims hold:

Base case: The single-vertex-tree satisfies $|E(T)| = |V(T)| - 1$ .

This is true, because 0 = 1 – 1.

Inductive step: If $T$ is a tree such that $|E(T)| = |V(T)| - 1$ , and $T^{\prime}$ can be obtained by adding a leaf to $T$ , then $|E(T^{\prime})| = |V(T^{\prime})| - 1$ .

Proof: Suppose $T$ is a tree such that $|E(T)| = |V(T)| - 1$ . Then, since $T^{\prime}$ results from adding a leaf to $T$ , we see that $|E(T^{\prime})| = 1 + |E(T)| = 1 + |V(T)| - 1 = (1 + |V(T)|) - 1 = |V(T^{\prime})| - 1$ .

Why does this prove that $|E(T)| = |V(T)| - 1$ for all trees $T$ ? Say that a tree $T$ has property $P$ if $|E(T)| = |V(T)| - 1$ . Our inductive step says that property $P$ is preserved under addition of a leaf. When we start out with something that has property $P$ , and change it by adding a leaf, we end up with something that still has property $P$ . With this in mind, pick an arbitrary tree $T$ . We know that $T$ is the result of starting from a single vertex and repeatedly adding leaves. A single vertex has property $P$ , by our base case. Since property $P$ is preserved under addition of a leaf, we can work our way up to $T$ , and conclude that $T$ has property $P$ .

One way to visualize this is to consider the space of all trees (depicted below), with each tree acting as a vertex in some “meta-graph.” Draw an edge directed from a tree $T$ to another tree $T^{\prime}$ if $T^{\prime}$ can be obtained by adding a leaf to $T$ . We know the single vertex tree tree has property $P$ , by our base case, and so this is our starting point.

Now, at each step, expand outwards to any unvisited tree neighboring a tree we’ve already visited.

At first this means visiting just the path on two vertices:

How can we be sure that this newly visited tree has property $P$ ? This is our inductive hypothesis: when we visit a new tree in the meta-graph, this tree must result from adding a leaf to a tree that we already know has property $P$ . Therefore, since property $P$ is preserved under addition of a leaf, the newly visited trees also have property $P$ .

Step 2:

Step 3:

Step 4:

Since every tree can be obtained by starting from a single vertex and repeatedly adding leaves, this breadth-first search in the meta-graph will, after enough steps, visit any given tree in this space. Like a virus, property $P$ infects every tree, with the single-vertex-tree acting as patient 0. This shows that every tree has property $P$ , as desired.

Since property $P$ is preserved under the addition of a leaf, we can say that “leaves are a configuration reducible with respect to property $P$ .” (Note: I don’t actually know if the term “reducible” is applied in non-planar contexts, but why not?) The term reducible refers to the fact that we can reduce the problem of proving property $P$ for a tree $T$ to the problem of proving property $P$ for ( $T - \text{any leaf of } T$ ). Any solution to the second problem gives us an easy solution to the first problem.

Here’s another example. We say that a graph is planar if it can be drawn so that no two edges intersect (other than at vertices). We say we can color a graph with $k$ colors if we can assign every vertex a number from the list $(1,2,...,k)$ so that no edge has endpoints of the same number. The degree of a vertex in a graph is the number of edges coming out of the vertex.

Theorem 2: Every planar graph can be colored with $6$ colors.

We use the fact that every planar graph has a vertex of degree at most $5$ (there are many proofs of this online, if the reader is interested). Similar to the previous example, this implies that any planar graph can be built up by starting from the empty graph and repeatedly adding vertices with degree at most $5$ directly after being added. (When we add a “degree- $n$ vertex”, we add a vertex whose degree is $n$ in the graph obtained directly after adding the vertex).

Base case: The empty graph satisfies the theorem.

Inductive step: Suppose $G$ is a planar graph that can be colored with $6$ colors. Then any graph $G^{\prime}$ obtained by adding a vertex of degree at most $5$ to $G$ can be colored with $6$ colors.

Proof: Suppose $v$ was added to $G$ to get $G^{\prime}$ . First color $G$ (i.e. assign the vertices of $G$ colors in the required way), then add $v$ , and assign $v$ a color. $G$ can be colored with $6$ colors, by assumption. Since $v$ has degree at most $5$ , there is at least one color left to spare for $v$ . Thus $G^{\prime}$ can be colored with $6$ colors.

Here, the property “can be $6$ -colored” was found to be preserved under addition of a vertex whose degree is at most $5$ . Since the empty graph has this property and every planar graph can be built up by repeatedly adding such vertices, we obtain the desired conclusion. To use a previous analogy, the breadth-first-search representing which planar graphs can be $6$ -colored visits the entire space of planar graphs. And to use previous terminology, vertices of degree at most $5$ are a configuration which preserve the property “can be $6$ -colored.”

Our final example concerns planar graphs that have no $4$ -cycles. So far, our graph theory problems could all have been solved using basic inductive techniques. This one is a bit more complicated.

A $4$ -cycle is, informally speaking, a subgraph (or graph) that is a closed loop with four vertices. Formally, it is a sequence of four vertices $(v_1, v_2, v_3, v_4)$ such that there are edges between consecutive terms in this list, and between $v_1$ and $v_4$ . An independent set in a graph is a set of vertices such that for every pair of vertices in the set, there is no edge between them. The independence ratio of a graph is the ratio of the number of vertices in the graph to the size of the largest independent set. I actually co-authored a paper which showed that the independence ratio of any four-cycle free planar graph is at most $4 - 1/30$ .

This is where the inductive machinery we’ve been building up throughout this post comes into play. Don’t worry too much about the details, because I’m only going to present a very rough outline of the proof anyways. We ended up proving that every $4$ -cycle-free planar graph has an independent set as large as some function of the number of vertices, the number of edges, and some other complicated stuff (see below).

If $G$ is a graph without any 4-cycles, then the following holds:

$\alpha(G) \geq |V(G)| - (19/34|V(G)| + 3/34|E(G)| + 3/34\lambda(G))$ .

Here, $\alpha(G)$ is the size of the largest independent set in $G$ , and $\lambda(G)$ is the number of components of $G$ equal to a triangle or to two triangles connected by an edge.

This was enough to prove the main result about independence ratio. The details aren’t necessary for understanding the proof in broad terms, but I’ve left an arXiv link at the bottom of this post for anyone interested in them. So, in keeping with the previous examples, say that a $4$ -cycle-free planar graph has property $P$ if it has a sufficiently large independent set relative to the number of vertices and all that other jazz (refer to the inequality displayed above). We started by finding some configurations which, when added to a graph, obviously preserve property $P$ . One example is a vertex with degree $0$ . If we have a graph with property $P$ , and we add a vertex with degree $0$ , we end up with a graph with property $P$ . On the one hand, when we add such a vertex, the number of vertices increase, so the criteria for having property $P$ become harder to meet. But, we have an entire additional vertex to use in any independent set, since this newly added vertex has no edges coming out of it. So, it turns out that this configuration, when added to a graph, preserves property $P$ . (In fact, addition of an isolated vertex preserves the property “has independence ratio of one”, leading correctly to the conclusion that if $G$ is a graph with only isolated vertices, then $\alpha(G) = |V(G)|$ ).

Thus, in our breadth-first-search marking which graphs have property $P$ , we can visit the isolated vertex, and all of its derivatives.

Next, we find that the addition of a degree-one vertex preserves property $P$ . Thus, we can add it to our set of configurations which preserve property $P$ . This allows us to visit even more graphs, like the path on two vertices, or on three vertices, or of any length.

All of these newly visited graphs are guaranteed to have property $P$ , because they can be built up by adding isolated vertices and degree-one vertices to the empty graph. This also includes paths with isolated vertices sitting idly by.

Thus, if there is a counterexample to the theorem, it has an edge and is not a path together with some isolated vertices. Our next configuration is a degree- $2$ vertex and is part of a triangle. This allows us to visit another class of graphs, which I’ll leave as an exercise to work out. As we added more and more configurations which preserve property $P$ , we guaranteed property $P$ for a larger and larger set of graphs. The breadth-first-search representing which graphs were visited grew larger and larger, while the set of possible counterexamples (the set of unvisited graphs) shrank and shrank. When this set was finally empty, we had finished proving that every $4$ -cycle-free planar graph has property $P$ . Below is a list of configurations, displayed in the order they were added to our set. Why does the order matter? Well, in order to prove that a certain configuration preserves property $P$ , it is often useful to know that certain other configurations preserve property $P$ .

Graph theorists often call such a list a set of unavoidable, reducible configurations. Each configuration in our set is reducible because each configuration preserves property $P$ . Our configurations are collectively unavoidable because any four-cycle-free planar graph can be built up by starting from the empty graph and repeatedly adding one of these configurations.

Note that if we had to proof a different theorem, like the $4$ -Color Theorem, this set of configurations would be neither unavoidable nor reducible. Some of these configurations do not preserve $4$ -colorability, like the vertex of degree $100$ (appearing fifth in the list).

To conclude, the theory of reducible configurations provides a general template for constructing inductive proofs, in settings more complex than that of natural numbers. If we want to prove that some property $P$ applies to every member of an infinite set $S$ , we can do the following:

1. Redescribe the set $S$ as the set of things you can get by starting from some base structure and successively making changes, with each change coming from some set $(\text{change}_1, \text{change}_2,...)$ .

2. Show that property $P$ is preserved under each of the changes in the set. You can’t lose property $P$ by making one of those changes.

3. Show that the property $P$ applies to the base structure.

4. Conclude that the property $P$ applies to every member of $S$ .

This format is implicitly invoked in every inductive proof, and is usually explicitly invoked whenever the set $S$ is defined recursively. This is the case in many proofs about the set of propositional formulas, for example (consider the proof of soundness for propositional logic).

Link to paper: https://arxiv.org/pdf/2305.02414.pdf

analogiesbetweenanalogies

Induction on Graphs: Reducible Configurations

Leave a comment Cancel reply

Induction on Graphs: Reducible Configurations

Share this:

Leave a comment Cancel reply