Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science March 3, 1998, 7pm Professors Nancy Lynch and Srini Devadas

Notes for Recitation 3 (2/20/98)

1 Buildup Error

“Buildup error” is a common source of mistakes in inductive proofs. We saw an example in lecture yesterday. Let’s look at another example.

False Theorem: If every vertex in a vertex-colored simple graph is adjacent to a vertex of the same color, then the graph is monochromatic.

Class exercise. Exhibit a simple counter-example to this claim.

Solution: A cycle on four vertices with two red vertices followed by two blue vertices. Each vertex is adjacent to some vertex of the same color, but the graph is not monochromatic.

(THIS IS PROOF IS PART OF THE TEAM PROBLEM HANDOUT.)

False Proof: By induction on the number of vertices in the graph. Let P (n) be the predicate, “If every vertex in an n-vertex vertex-colored simple graph is adjacent to a vertex of the same color, then the graph is monochromatic.”

In the base case, P (1), the graph contains only one vertex and so is certainly monochromatic.

For the inductive step, we assume P (n) in order to prove P (n + 1). For n ≥ 1, let G = (V, E) be a vertex-colored graph with n + 1 vertices such that every vertex is adjacent to a vertex of the same color, and let v ∈ V be an arbitrary vertex. Let G′ be the subgraph of G obtained by deleting v. Since G′ is an n-vertex graph, we have by induction that G′ is monochromatic. By hypothesis, v is adjacent to a vertex v′ of the same color. Since v′ must be a vertex of G′, it follows that v has the same color as all the other vertices. Therefore, G is indeed monochromatic.

Class Exercise. Pinpoint the flaw in this proof.

Solution: the flaw is in the statement, “Since G′ is an n-vertex graph, we have by induction that G′ is monochromatic.” This is incorrect. We can assume only that if every vertex in G′ is adjacent to a vertex of the same color, then we have by induction that G′ is monochromatic.” Unfortunately, removing v from G may yield a G′ for which the adjacency condition fails.

The correct assumption does not apply to G′ and does not lead to a proof. Of course a breakdown of the proof was inevitable, since the theorem is false!

Class exercise: Verify that the red/blue 4-cycle above is example where the adjacency assumption fails for G′.

Solution: We saw red/red/blue/blue 4-cycle satisfies the adjacency condition. Now remove, say, a red vertex. Resulting graph red/blue/blue graph leaves red vertex w/o a red neighbor.

2 Well-Ordering

There is another variation of induction that is sometimes useful: well-ordering. The well-ordering axiom looks nothing like the induction axiom:

Axiom 2.1 Every nonempy set S ⊆ ℕ has a smallest element.

The well-ordering axiom is often called the well-ordering principle. It may seem obvious and useless!

As for obvious, note that this axiom would be false if the set of non-negative integers, ℕ, were replaced by, say, the set of non-negative rational numbers; then for example the subset consisting of the positive rational numbers has no smallest element. It would also be false if ℕ was replaced by the set of all integers; then the whole set has no least element.

As for useless, it may be surprising that everything that can be proven by induction can also be proven using the well-ordering principle! It’s not hard to prove this metamathetical fact, but we won’t bother. We’ll just illustrate a typical use of the Well-Ordering Principle.

Here is a special case of the Principle of Inclusion-Exclusion which we’ll take up in a few weeks.

Theorem 2.2 For all finite sets A, B

|A ∪ B| = |A| + |B| − |A ∩ B|.

Rosen, Section 1.5, Example 5 gives a simple explanation for this equality: take the set A ∪ B and mark each element of A and then mark each element of B. So the total number of marks is |A| + |B|. The elements in A ∩ B now wind up with two marks, while the others get one mark. If we now remove one mark from each element in A ∩ B, we are left with a total of |A| + |B| − |A ∩ B| marks. Since each element of A ∪ B is now left with exactly one mark, this last total must equal |A ∪ B|.

This is a pretty good argument which we would actuallly accept as a proof later in the term—after we’ve had more experience recognizing when such an argument can be reduced to careful reasoning about numbers, functions, and sets. But at this point in the term, the concepts of “marking” and the rules for their bookkeeping remain too fuzzy for comfort. So let’s prove the theorem with careful, elementary reasoning.

We’ll need three simple facts relating set size to set operations in the proof.

Fact 1 Any subset of a finite set is finite.

Fact 2 |A| = 0 iff A = ∅.

Fact 3 If A is a finite set and x ∉ A, then |A ∪ {x}| = |A| + 1. In other words, if we add a new element to a set, it gets larger by one.

We could prove these three facts themselves from the definition of the cardinality, |A|, of a finite set, A, using simple reasoning about sets, but they are so simple and familiar that we’ll take them for granted. (Definition 4 of Rosen, Section 1.4 claims to specify the cardinality of a finite set, but it’s not very crisp. The precise mathematical definition is that for n ∈ ℕ, |A| is defined to be n iff there is a bijection from the integers 1, …, n to A. And A is finite iff |A| = n for some n ∈ ℕ.)

Proof by contradiction: We will suppose the inclusion-exclusion equality fails for some finite A, B and reach a contradiction.

Suppose the equality fails for some finite A, B. By Fact 1, A − B is also finite. By the Well-Ordering Principle, there must therefore be finite sets A, B for which the equality fails and such that |A − B| is minimum among all such sets.

Note that by Fact 2, |A − B| = 0 iff A − B = ∅ iff A ⊆ B. But the inclusion-exclusion equality clearly holds when A ⊆ B, so we conclude that A − B ≠ ∅, that is, there is some element a ∈ A − B.

Let A′ = A − {a}. From Fact 3

|A| = |A′| + 1.

Similarly, A ∪ B = (A′ ∪ B) ∪ {a} and a ∉ A′ ∪ B, so by Fact 3

|A ∪ B| = |A′ ∪ B| + 1.

Likewise, A − B = (A′ − B) ∪ {a} and a ∉ A′ − B, so

|A − B| = |A′ − B| + 1.

In particular, |A′ − B| < |A − B|. Finally, since a ∉ B, we have that A ∩ B = A′ ∩ B, so

|A ∩ B| = |A′ ∩ B|.

Since |A′ − B| < |A − B| and |A − B| was minimum for the equality to fail, the equality must hold for A′, B, that is,

|A′ ∪ B| = |A′| + |B| − |A′ ∩ B|.

Hence,

|A ∪ B| = |A′ ∪ B| + 1
= |A′| + |B| − |A′ ∩ B| + 1
= |A′| + 1 + |B| − |A ∩ B|
= |A| + |B| − |A ∩ B|

contradicting the fact that the equality fails for A, B.

As we noted, Well-Ordering proofs can always be reformulated as proofs by induction, and vice-versa. In particular, the Well-Ordering proof above can easily be transformed into a proof by induction on the size of A − B, as the reader should check.

Team Problems

Problem 1. How many simple graphs (up to isomorphism) are there with |V | = |E| = 5?

Solution: If two graphs are isomorphic, then they have the same size maximum cycle. This should be clear. If they don’t, then there is no labelling of the vertices that will make the two graphs identical, because one will have the cycle V_{1}, V_{2}, V_{3}, … V_{n} and the other will not have such a cycle. So for this problem, one only needs to consider the number of isomorphic graphs for each size of maximum cycle. If the maximum cycle is five, there is only one graph, and the entire graph is that cycle. If the maximum cycle is four, there are two graphs, one with one connected component, and one with two connect components. Finally, if the maximum cycle is three, there are three graphs, depending on how the missing two vertices are connected to the 3-cycle.

Problem 2. Let A be the adjacency matrix for a digraph G with n vertices. Note that A is a zero-one valued n × n matrix. In this problem we use the Boolean “OR” operation, ∨, instead of “+” when multiplying zero-one valued matrices (this is called “boolean” matrix product).

(a) For k ∈ ℕ, let A^{k} be the kth Boolean power of A. Prove that A^{k}_{ij} = 1 iff there is a directed path of length k from the ith to the jth vertices of G. Solution: Proof: by induction on k.

Inductive Hypothesis: P (k) : A^{k}_{ij} = 1 iff there is a directed path of length k from the ith to the jth vertices of G.

Base Case: k = 1. By the definition of an adjacent matrix A, A_{ij} = 1 iff there is a directed edge (directed path of length k = 1) from the ith to the jth vertices of G.

Inductive Step: Assume P (k) to prove P (k + 1).

A^{k}_{ij} = ⋁_{l∈G}(A^{k}_{il} ∧ A_{lj})

Now we consider both directions for the iff. Case 1: There is a directed path of length k + 1 from the ith to the jth vertices of G. This path looks like i, i_{1}, i_{2}, … i_{k}, j. Then consider l = i_{k}. A^{k}_{il} = 1 (inductive hypothesis). A_{lj} = 1 (there is an edge from i_{k} to j), under the Case 1 assumption. Therefore

(A^{k}_{il} ∧ A_{lj}) = 1
A^{k}_{ij} = 1

Case 2: A^{k+1}_{ij} = 1. Then ∃l ∈ G : (A^{k}_{il} ∧ A_{lj}) = 1. Thus there is an edge from l to j and there is path of length k from i to l(by the inductive hypothesis) which looks like i, i_{1}, i_{2}, … i_{k−1}, l. Thus, there is a path of length k + 1 from i to j which hits l on the kth step and then has the k + 1st edge from l to j. This path follows the vertices: i, i_{1}, i_{2}, … i_{k−1}, l, j.

Q.E.D.

(b) Let B = A ∨ I where I is the n × n identity matrix. Prove that B^{k}_{ij} = 1 iff there is a directed path of length ≤ k from the ith to the jth vertices of G. Solution: From part a, it can be seen that B^{k}_{ij} = 1 iff there is a directed path of length k from the ith to the jth vertices of G′, where G′ is the graph described by the adjacency matrix B. Since G′ is just G with self loops, a path exists between i and j in G′ iff a path exists between i and j in G (all vertices have paths of length 0 to themselves). For any such path between i and j in G′, either it uses a self-loop edge or it does not. If it does not, then the equivalent path in G will have the same length. If it does, then there is a shorter path in G which can be obtained by not using the self loop. So if there is a path of length k between i and j in G′ then there is a path of length ≤ k between i and j in G. If there is a path of length ≤ k between i and j in G, then it can be made to be of length k by using self loops to lengthen the path. Thus there is a path in G′ of length k iff there is a path in G of length ≤ k. Since B^{k}_{ij} = 1 iff there is a path of length k between i and j in G′ then B^{k}_{ij} = 1 iff there is a path of length ≤ k between i and j in G.

(c) Conclude that B^{n}_{ij} = 1 iff there is a directed path from the ith to the jth vertex. Solution: If B^{n}_{ij} = 1 then there is a directed path from the ith to the jth vertex. If B^{n}_{ij} = 0 then there is no path of length <= n from the ith to the jth vertex. There must also be no path of length > n from the ith to the jth vertex. If there were, then the path must cross through some vertices twice, since the length of the path is > n. For those vertices through which the path passes twice, eliminate the loops so that the path uses no vertex more than once. This means the path must be of length <= n, which reaches a contradiction, since we know that there are no paths from i to j of length <= n. Therefore, if B^{n}_{ij} = 0 there is no path from i to j at all.

Problem 3. The complement, \overline{G}, of a simple graph, G, is defined to be the graph which has the same vertices as G such that two vertices are adjacent in \overline{G} if and only if they are not adjacent in G.

(a) A subset, A, of the vertices of a simple graph, G, such that no two vertices in A are adjacent in G, is called an anti-clique of G. Prove that G contains an anti-clique of size m iff \overline{G} contains a copy of K_{m}.

Solution: Both directions must be proven. Suppose G contains an anticlique A of size m. Then ∀a ∈ A∀b ∈ A(a ≠ b) : ((a, b) ∉ G). Therefore ∀a ∈ A∀b ∈ A(a ≠ b) : ((a, b) ∈ \overline{G}, so \overline{G} contains a copy of K_{m}.

Suppose \overline{G} contains a copy of K_{m} called A. Then ∀a ∈ A∀b ∈ A(a ≠ b) : ((a, b) ∈ \overline{G}). Therefore ∀a ∈ A∀b ∈ A(a ≠ b) : ((a, b) ∉ G). Therefore G contains an anti-clique of size m.

(b) A simple graph, G, is called self-complementary iff G and \overline{G} are isomorphic. Prove that if G is a self-complementary simple graph with n vertices, then

n ≡ 0 (mod 4) or n ≡ 1 (mod 4).

Hint: How many edges altogether are there in G and \overline{G}?

Solution: The sets of edges for G and \overline{G} are disjoint and together make up all edges in the complete graph K_{n}. K_{n} contains n(n − 1)/2 edges. Since G and \overline{G} are isomorphic, they have the same number of edges, namely n(n − 1)/4. Since this number must be an integer, either 4|n or 4|(n − 1). So n ≡ 0 (mod 4) or n ≡ 1 (mod 4).

(c) For integer n > 0, define a simple graph G_{n} as follows: the vertices are the integers 1, 2, …, 2n. Vertices i ≠ j are adjacent iff i, j ≤ n or (i ≤ n and j > n and i ≡ j (mod 2)). Prove that G_{n} is not (n − 1)-colorable. Solution: Since all vertices ≤ n are adjacent to each other, G_{n} contains K_{n}. K_{n} requires n colors to color, so G_{n} is not (n − 1)-colorable.

(d) Prove that G_{n} is self-complementary.

Solution: The graphs are isomorphic. Consider the labelling of G_{n}. Then label \overline{G}_{n} such that for a particular vertex i ∈ G_{n}, it’s number in \overline{G}_{n} is 2n + 1 − i. Vertices are adjacent in G_{n} iff i, j ≤ n or i ≤ n and j > n and i ≡ j (mod 2). Therefore, vertices in G_{n} are not adjacent iff i, j > n or i ≤ n, j > n and i ≡ j + 1 (mod 2). Thus, in \overline{G}_{n}, vertices are adjacent iff i, j > n or i ≤ n, j > n and i ≡ j + 1 (mod 2). Under the isomorphism labelling for \overline{G}_{n}, this is equivalent to saying that vertices are adjacent iff (2n + 1 − i), (2n + 1 − j) ≤ n or (2n + j − 1) ≤ n, (2n + i − 1) > n and (2n + j − 1) ≡ (2n + i − 1) (mod 2). We want to show that vertices in \overline{G}_{n} are adjacent iff their partners in G_{n} are adjacent. By the labelling, the statement (2n+1−i), (2n+1−j) ≤ n or (2n+j −1) ≤ n, (2n+i−1) > n and (2n + j − 1) ≡ (2n + i − 1) (mod 2) is the same statement as i, j ≤ n or j ≤ n, i > n and j ≡ i (mod 2). So vertices in \overline{G}_{n} are adjacent iff their partners in G_{n} are adjacent. Since this shows that the labelling results in identical graphs, G_{n} and \overline{G}_{n} are isomorphic, so G_{n} is self-complementary.

Problem 4. Let G be a simple graph with n > 0 vertices. Prove that if G has no vertex of degree ≥ m, then G has an anti-clique of size ≥ n/m.

Solution: By strong induction on the number of vertices of G.

The base case n ≤ m follows by choosing the anti-clique to consist of a single vertex.

So for the induction case, suppose n > m. Pick any vertex of, v, of G. Remove v and all vertices adjacent to v from G; call the remaining graph, H. Now H has at least n − m vertices because v has degree < m, and by definition of H, none of the vertices in H are adjacent (in G) to v. Since removing vertices does not increase degrees, H also has no vertex of degree ≥ m. By strong induction, there is an anti-clique A of H of size at least (n − m)/m = n/m − 1. So A ∪ {v} is an anti-clique of G of size at least n/m.

THE FOLLOWING PROBLEM WAS NOT USED. IT’S MORE SUITABLE FOR LECTURE OR PSET PRESENTATION.

Problem 5. We have seen that both a graph and its complement may require a lot of colors. (In fact G_{n} and hence \overline{G}_{n} each contain a copy of K_{n}, so neither is (n − 1)-colorable.)

Is it possible to have a large graph such that both it and its complement do not require a lot of colors? A famous theorem of Ramsey implies that this cannot happen—either the graph or its complement must require a lot of colors. More precisely,

Theorem (Ramsey): Let m and l be positive integers, and G be a simple graph. If G has ≥ m^{l} vertices, then either G contains a copy of K_{l} (and hence G is not l colorable) or \overline{G} contains K_{m} (and hence \overline{G} is not m colorable).

Prove the Theorem. Hint: Induction on l. There are two cases, (1) when every vertex of G has degree < m^{l}, or (2) when some vertex does have degree ≥ m^{l}. The Lemma above handles case (1).

Solution:

The base case l = 1 follows because m^{1} ≥ 1, and every graph with at least one vertex has K_{1} as a subgraph.

So assume that G has at least m^{l+1} vertices. There are two cases:

(1) Every vertex of G has degree < m^{l}. Then by the Lemma, G has an anti-clique of size at least m^{l+1}/m^{l} = m, so \overline{G} contains K_{m}.

(2) Some vertex, v, of G has degree > m^{l}. Let H be the subgraph obtained by restricting G to the vertices adjacent to (and not including) v. Now H has ≥ m^{l} vertices, so by induction, either H contains K_{l} or \overline{H} contains K_{m}.

Note that \overline{H} is the restriction of \overline{G} to the vertices in H. So if \overline{H} contains a copy of K_{m}, so does \overline{G}, and the Theorem holds. Otherwise, H contains a subgraph, C, which is a copy of K_{l}. So C ∪ {v} is the required copy of K_{l+1} in G.