Massachusetts Institute of Technology Handout 16 6.042J/18.062J: Mathematics for Computer Science February 19, 1998 Professor Albert R. Meyer

Notes for Tutorial 3 (2/19/99)

1 Buildup Error

“Buildup error” is a common source of mistakes in inductive proofs. We saw an example in lecture; here’s another:

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.

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 Bipartite Graphs

Recall that a graph is k-colorable if every vertex can be assigned one of the k colors so that no adjacent vertices have the same color. A 2-colorable graph is called bipartite. Many common types of graph are bipartite, and they often arise in computer science.

Theorem 2.1. Every tree is bipartite.

Before proving this theorem, we’ll first prove a lemma about trees.

Lemma 2.2. Every tree with more than one vertex has a vertex of degree one.

Proof. The proof is by contradiction. Suppose that there is an n-vertex tree that has no vertex of degree one. Since the tree is connected and has more than one vertex, no vertex can have degree zero. As a result, every vertex must have degree at least two. Since the number of edges in a graph is half the sum of the degrees, the number of edges must be at least \frac{1}{2}(2n) = n. This contradicts the fact that an n-vertex tree has exactly n − 1 edges.

Now we can use the lemma to prove the theorem that every tree is bipartite.

Proof. The proof is by induction. Let P (n) be the predicate that every tree with n vertices is bipartite. In the base case, P (1) is true because a graph consisting of a single vertex can be colored with just one color. In the inductive step, for n ≥ 1 assume that every tree with n vertices is bipartite in order to prove that every tree with n + 1 vertices is bipartite.

Let G be a tree with n + 1 vertices. By the lemma, we can pull off a vertex v with degree one. The remaining n-node graph is a tree. (The reason is that we removed one node and one edge and did not introduce a cycle. Therefore, the remaining graph is acyclic and has n nodes and n − 1 edges. This defines a tree.) By induction, the remaining graph is bipartite. The extra vertex v can take whatever color that its single neighbor does not.

3 Counting Graphs

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

Solution: Since |V | = |E| > |E| − 1, any such graphs must have a cycle. If two graphs are isomorphic, then they must have the same size maximum cycle. (This should be clear). So we can classify graphs by 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 connected components. If the maximum cycle is three, there is one disconnected graph and two connected graphs, depending on how the two vertices not in the cycle are (or are not) connected to the 3-cycle. Since by definition a cycle must be of size at least three, we are done.

4 Posets

The connectedness relation of a DAG is a partial order. These come up in Computer Science all the time. The Course Scheduling example from lecture was one illustration of the application of partial order concepts.

Remember that in a digraph, vertex u is said to be connected to vertex v iff u = v or there is a path from u to v. If we write u ⪰ v to mean that u is connected to v, then ⪰ is a binary relation on the vertices which is obviously transitive:

[u ⪰ v ∧ v ⪰ w] ⟹ u ⪰ w,

and, because the digraph has no cycles, it is antisymetric:

[u ⪰ v ∧ v ⪰ u] ⟹ u = v.

Formally, a partial order on a set is just a binary relation which is transitive and antisymetric^{1}.

The coordinatewise ≥ relation on n-bit vectors a, b is a simple example of a partial order: define a ⪰ b iff a_{i} ≥ b_{i} for 1 ≤ i ≤ n. Here’s a DAG with V = {0, 1}^{3} whose connectedness relation is exactly the same as ⪰:

DRAW THE CUBE WITH DIRECTED EDGES DOWN.

1Rosen also requires that a partial order be reflexive: v ⪰ v for all v. In 6.042 we will not always insist on reflexivity. For example, we will consider the relation v ≻ u — defined to mean that there is a directed path (which by definition is of positive length) from vertex u to v — to be a nonreflexive partial order on the vertices of a DAG. Note that the connectedness relation, ⪰, of a DAG is in fact reflexive by our definition, because we explicitly specify that every vertex is connected to itself.

Two elements u and v are said to be comparable under a partial order, ⪰, iff either u ⪰ v or v ⪰ u; otherwise, u and v are incomparable. For example, 100 and 010 are incomparable elements in the cube above.

The most familiar example of a partial order is the order < on real numbers. This partial order is a special one because it is actually a total order. The totality property says that every two elements are comparable:

∀u ≠ v : u < v ∨ v < u.

Notice that if ⪰ is a partial order, so is ⪯ defined by the rule that u ⪯ v iff v ⪰ u. Sometimes we don’t want to prejudice whether we’re thinking of a partial order as “bigger than” or “smaller than,” so we choose some symbol like R for the relation and write uRv instead of u ⪰ v.

Technically, a partial order is always defined on some set P. The set together with the partial order is called a partially ordered set or poset.

Examples:

1. (ℕ, |) is a poset. That is, the “divides” relation | is a partial order on the set of natural numbers. It is not total (WHY? – because, eg, neither 3|5 nor 5|3.) Note that if we talk about divides as a “smaller-than” relation, then zero is a maximum element, namely smaller than every other element, and one is a minimum element.

2. QUESTION: why isn’t (ℤ, |), a poset?

3. (P (ℕ), ⊆) is a poset. That is, the containment relation is a partial order on the subsets of natural numbers. It is not total (WHY? – because, eg, neither {3} ⊆ {5} nor {5} ⊆ {3})

4. Dictionary order on words over the English alphabet is a total order.

5 Team Problems

Problem 1. Define a DAG to be connection-minimal iff no edge can be deleted from it without changing the connectedness partial order on the vertices of the DAG.

(a) Describe a connection-minimal four-vertex DAG with as few edges as possible. Solution no edges.

(b) Describe all the connection-minimal DAG’s with three vertices. Solution: vertical line of three, V, and Wedge, all directed down, are the only connected cases. There’s one case with exactly 2 connected, and one case w/none connected.