6
$\begingroup$

This may be a trivial question, but I'm a little confused about something. My graph theory instructor had said while using induction proofs (say on the number of edges ($m$)), that one must not build the $m+1$ edged graph from the induction step. Instead, one must take any $m+1$ edged graph, delete an edge and then use the induction case. I understand this second approach seems "more correct" but I can't pinpoint why.

I think perhaps inserting a new edge in a graph with $m$ edges (where we assume our hypothesis works) builds a graph specific to where I'm inserting that edge and the statement is proven for that particular graph, instead of the general class of all $m+1$ edged graphs. But if we do not specify where we are inserting a new edge, is this not equivalent to working with any graph with $m+1$ edges? What am I missing here? Can someone give a counterexample where upon inserting a new edge a hypothesis apparently seems true, but is actually false for other classes of $m+1$ edged graphs?

$\endgroup$
2
  • $\begingroup$ if you have a set of graphs with $m$ edges where a property holds, it's not sure that you can build any $m+1$ edges graph just by adding one edge to one of your graphs $\endgroup$
    – Exodd
    Commented Jul 7, 2022 at 13:59
  • $\begingroup$ But in the induction step, we assume our property holds true for any $m$ edged graph. Can we not build any $m+1$ edged graph by adding an edge to one of them? $\endgroup$ Commented Jul 7, 2022 at 14:01

3 Answers 3

3
$\begingroup$

I have seen false proofs with such flaws here in MSE but I don't remember the details of any specific case.

I think there was a case where the induction step was adding a new vertex and an edge to it, so it was adding a degree 1 vertex. The claim was that this proof showed the property was true for all graphs that had at least one degree 1 vertex.
This is of course false - it proves it only for tree graphs.

Here is a more subtle abstract example. Suppose I want to prove: Every graph with property A also has property B. I'll use induction on the vertices, and find that the graph with a single degree zero vertex has both those properties so the base case holds. I then want prove an induction step. If I take any graph with $n$ vertices that has property A, which by assumption also has property B, and add a new vertex and its edges to it in such a way that property A still holds, then I am able to prove it will always also have property B. This proves the result, right?

Well no. There can still be a graph with $n+1$ vertices that has property A but not property B. It just so happens that if you delete any vertex from that graph, it loses property A. It simply cannot be built up directly from a smaller graph with property A, and is therefore completely bypassed by the induction step.

There are many properties for which the above is impossible. For example, if you're doing induction on the number of vertices, then connectedness works fine for property A because there is always at least one vertex that can be removed while still keeping the graph connected. So conversely, you can build up any connected graph vertex by vertex whilst always remaining connected. For other properties, especially when you are doing induction on the edges rather than the vertices, it is not always so clear whether it works or not.

Even if property A is a safe property to use when building up graphs edge by edge, you still would have to be sure that you've checked all possible ways to build an A-graph with $n+1$ edges from all possible A-graphs with $n$ edges. There must be no subtle hidden assumption that causes you to miss out some graphs resulting in an incomplete proof.

Therefore it is best to do things as follows:

  1. Start with any graph with $n+1$ edges that has property A.
  2. Show that you can remove an edge in such a way that property A still holds.
  3. This smaller graph also has property B by the induction hypothesis.
  4. Show that after adding the edge from step 2 back in, property B remains.

If you skip steps 1 and 2, you are assuming without proof that all A-graphs can be directly built from smaller A-graphs, and run the risk of overlooking some ways of adding the edges back in. Steps 1 and 2 let you home in on exactly what you need from the smaller graph to build the larger one.

$\endgroup$
3
$\begingroup$

I would say that in this case you are correct: these two cases are exactly symmetric, and either proof would be equally valid.

However, there is a subtlety here, and it may be worth reflecting on.

Suppose that instead of doing induction on the number of edges, you do induction on the number of vertices. You are proving the induction step, so you assume that your theorem holds for graphs with $n$ (or fewer) vertices, and now you want to prove that it holds for graphs with $n+1$ vertices. Thus, you take some arbitrary graph with $n$ vertices, and you turn it into a graph with $n+1$ vertices by just adding one more disconnected vertex to it. You prove your induction step, and voila, you're done.

Of course what I just wrote does not work: the induction step has not proved it for all $n+1$ vertex graphs, just for those with at least vertex with degree 0, so the whole proof falls apart. (For example, with this "induction" it would be easy to "prove" that all non-empty graphs have more vertices than edges.)

That is, if you separate all your structures $G$ (e.g., all finite graphs) into classes $G_0, G_1, G_2, \ldots$ (e.g. by the number of vertices or edges), and you have some way of turning elements of $G_i$ into elements of $G_{i+1}$ so that what you are proving transfers, this may not be enough.

Phrased another way: for the example in your question, you need to note that "each graph with $m+1$ edges can be made by adding an edge to a graph with $m$ edges" -- the 'delete' version of the argument does this for you. But this fact is so obvious, that insisting that it be made explicit strikes me as excessive.

$\endgroup$
1
  • $\begingroup$ I see. He probably meant the "breaking down" instead of "building up" in the context of vertices or something else. That makes sense, thanks! $\endgroup$ Commented Jul 7, 2022 at 14:06
2
$\begingroup$

What you're seeing here is a nuanced but important principle of how induction works more generally. It's not particular to graphs, though it often comes up there.

At a high level, in the inductive step of a proof, you assume whatever theorem you're trying to prove is true for some value of $n$, then prove it's true for $n+1$. However, that does not mean that you necessarily start with an object of size $n$, then try to build it into an object of size $n+1$. To see why, let's imagine you're trying to prove the following result by induction:

$$\text{Every tree with }n\text{ nodes has }n-1\text{ edges.}$$

This would mean that the statement you need to prove in your inductive step would look like this:

$$\begin{aligned} &\text{If} \\ &\qquad\text{every tree with } n \text{ nodes has } n-1 \text{ edges} \\ &\text{then}\\ &\qquad\text{every tree with } n+1 \text{ nodes has } n \text{ edges.} \end{aligned}$$

Now, how would you prove a statement like this? Well, you'd begin by assuming the antecedent, so we'd assume that every tree with $n$ nodes has $n-1$ edges. Importantly, this does not mean that we have a concrete choice of a tree. Rather, it means "if we can find a tree with $n$ nodes, then we can conclude that it has $n-1$ edges." So we make a note of that, keep it in our back pocket, and move onward.

We then need to prove the consequent. The consequent is "every tree with $n+1$ nodes has $n$ edges." That's a universally-quantified statement, so we pick an arbitrary tree with $n+1$ nodes, and now our goal is to prove that it has $n$ edges.

The net effect of all of this is that we began our proof not with a concrete choice of a tree of $n$ nodes and $n-1$ edges, but rather with a tree of $n+1$ nodes and an unknown number of edges. However, we also know that if we can find any tree with $n$ nodes, we can claim that tree has $n-1$ edges. That means that we will likely proceed through this proof by trying to find a way to remove one of the nodes from our $(n+1)$-node tree. This aligns with your professor's advice: start with a big object and make it smaller.

However, that doesn't mean that in every problem with graphs, you should start big and aim to make things smaller. Let's try proving another result:

$$\text{There is a graph with }2^n\text{ nodes where each node has degree }n\text{.}$$

Let's write out what we need to prove for our inductive step:

$$\begin{aligned} &\text{If} \\ &\qquad\text{there's a graph with } 2^n \text{ nodes, all of degree } n \\ &\text{then}\\ &\qquad\text{there's a graph with} 2^{n+1} \text{ nodes, all of degree } n+1 \text{.} \end{aligned}$$

Now, how would we prove this? Well, we begin by assuming the antecedent. The antecedent is existentially-quantified, which means we begin by assuming we have some actual graph with $2^n$ nodes that all have degree $n$. We're not saying that every graph with $2^n$ nodes has only nodes of degree $n$, rather that there's some specific one that we know of.

To prove the consequent, we need to prove an existentially-quantified statement: that there's a graph with $2^{n+1}$ nodes where each node has degree $n$. To do that, we'll need to find a way to actually build this object. And the easiest way to do that will probably be to start with our graph of $2^n$ nodes and to find a way to "grow" it to a larger graph with $2^{n+1}$ nodes.

Importantly, notice in this case that we did start with a smaller object, and our goal was to build it up into a larger object! Why is this proof different?

This boils down to how induction works when you're proving something universally-quantified versus existentially-quantified.

In the first case, where we were looking at a proof that all trees of $n$ nodes have $n-1$ edges, we were trying to prove a result about all trees with $n$ nodes. That means that we're proving something universally-quantified. Therefore, our induction step will begin by assuming something universally-quantified about objects of size $n$, which means we don't have a concrete choice of object of size $n$ in hand. We then need to prove something universally-quantified, where our first step will be to pick an arbitrary object of size $n+1$. In other words, we start with a larger object, then try to make it smaller.

In the second case, where we wanted to prove that there are graphs of size $2^n$ where all nodes have degree $n$, we're proving an existentially-quantified statement. That means that in our inductive step, we'll assume that there is some concrete object of size $n$, then try to prove that there is some concrete object of size $n+1$. In other words, we start with a smaller object, then try to make it larger.

As a general principle,

  • when proving something universally-quantified by induction, start with a larger object and make it smaller; and
  • when proving something existentially-quantified by induction, start with a smaller object and make it larger.

This applies outside of the world of graphs - nothing here is particular to graphs or graph theory. When I'm teaching discrete math to my students, this is often one of the harder lessons to learn, since it seems so counterintuitive!

Hope this helps!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .