Sheet J: Induction (Used in Graph Theory)

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk

So far we have concentrated on looking at how geometrical questions arise from questions about the world (street traversal problems, representing a polyhedron in the plane, visibility questions, etc.). However, as we discover new mathematical "facts" we need tools to be able to prove these results. One criticism of geometry, in contrast to other branches of mathematics (analysis, algebra), is that its methods often are "ad hoc." There is a "cute trick" to solve many individual problems but sometimes these "tricks" don't work for much else. One tool that is universally useful throughout mathematics is mathematical induction. In particular, it is useful in geometry and graph theory.

Mathematical induction is a theorem-proving tool that enables one to demonstrate that a statement S(n) (defined for n = 1, 2, .....) is valid for all values of n. (Sometimes the starting value of n will be 0 or some other positive integer than 1.) For example, S(n) might be the statement: If T is a tree with n edges, then T has n+1 vertices. Another example would be the statement S(n) (starting with n = 3): If T is a triangulated polygon (i.e. a simple polygon whose interior has been divided into triangles by adding diagonals between existing vertices of the polygon), then T can be a vertex colored with 3 colors. How can Mathematical Induction be used to prove statements like these?

The way mathematical induction works is that we have to carry out two steps to use this method to show that S(n) holds for all the values of n from some value beyond one that interests us.

The formal statement of mathematical induction is:

Given a collection of statements S(n) where for each value of n we get a
statement which we would like to verify is true.

1. If S(1) is true

2. If the truth of S(k) implies the truth of S(k+1)

In Step 2, the assumption of the truth of S(k) is usually referred to as the "induction hypothesis.

Conclusion:

S(n) is true for every value of n.

Sometimes it is helpful to think of mathematical induction in terms of the process of climbing an "infinite" ladder. To climb such a ladder one must be able to get to the first rung, and if one is on any given rung, one must be able to get to the next rung. If one can do both of these "tasks," then one can go on forever because one can get "started," and once in a particular place, can move up one step.

To prove that every tree with n edges has n + 1 vertices, call this statement S(n). S(1) states that every tree with one edge has two vertices. There is only one tree with one edge (all trees with one edge are isomorphic), so S(1) holds. Note that S(0) also holds. If T is a tree with zero edges, it has one vertex.

Now assume S(k).

Given: If T is a tree with k edges, then it has k+1 vertices.

Prove: If T* is a tree with k+1 edges, then it has k+2 vertices.

Since T* is a tree, as long as it is not the tree with a single vertex it will have at least two 1-valent vertices. Suppose w is one of these 1-valent vertices. Let T' be obtained from T* by deleting the vertex w and the edge that makes w 1-valent. Since T' has one edge less than T* which has k+1 edges, T' has k edges. However, we are "given" that any tree with k edges has k+1 vertices. Thus, T' has k+1 vertices. Now restore the vertex w and the edge attached to w to get back T*. We see that T* must have k+2 vertices.

We have verified S(1) and S(k) true means S(k+1) is true, hence, by the method of mathematical induction we can conclude that S(n) holds for all n.

Induction can also be used to show that every triangulated polygon can be 3-vertex colored. Even if one obtained the triangulation of the polygon by some method other than by cutting off "ears," one can prove that every triangulated polygon has at least 2 vertices of valence 2. Recall v is an ear of a polygon if the line segment joining the endpoints of the edges at v lies totally within the polygon. This follows from the fact that if one puts a dot in each triangular face of a triangulated polygon,with at least four sides, other than the unbounded face, and joins two such dots, if the triangles they represent share an edge, one must get a tree. Since (non-trivial) trees have at least two 1-valent vertices, we see that there are at least two 2-valent vertices in a triangulated polygon. In fact, if one proves that plane simple polygons can be triangulated by some other approach than the ear theorem, this idea can be used to prove Meister's Ear Theorem. The "hard step" in the induction is to show that if S(k) holds, then S(k+1) holds. To show that a triangulated polygon with k+1 vertices can be vertex colored with three colors, one can locate a 2-valent vertex of the triangulated polygon, remove the triangle at this vertex, and apply the induction hypothesis.

While induction proofs in "number theory" (e.g. show 1 + 3 + 5 .... + (2n - 1) = n2) often involve some "algebraic simplification" of an algebraic expression, in proofs in the area of geometry, one needs to at some stage employ a "geometrical fact" in order to move to a new geometrical result from one's previous state of geometrical knowledge. In the two examples mentioned above we used the geometrical facts that a tree with at least two vertices has at least two 1-valent vertices and that a triangulated simple polygon in the plane has at least two 2-valent vertices to prove other geometrical results.

If you are wondering what makes using mathematical induction valid, a version of this idea is built into the Peano Axioms for the integers. Using mathematical induction is right at the foundations of mathematics.

One of the most important results we will study this semester is Euler's Polyhedral Formula. Its graph theory version says that for a connected graph we have V + F - E = 2 where V, F, and E are the number of vertices, faces, and edges of the graph, respectively. The result is valid for both simple graphs (no loops or multiple edges) and graphs that have loops and multiple edges. This result can be proved by mathematical induction where the value of n used in the induction statement counts the number of vertices, faces, or edges. However, we will use two proof approaches other than mathematical induction that I hope you will find more insightful. One is based on an idea of Augustin Louis Cauchy (1789-1857) and the other is due to the German geometer Karl Von Staudt (1798-1867).