Sundry

Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)

1   Pebbles

Suppose you have a rectangular array of pebbles, where each pebble is either red or blue. Suppose that for every way of choosing one pebble from each column, there exists a red pebble among the chosen ones. Prove that there must exist an all-red column.

2   Contraposition

Prove the statement "if x + y < z + w, then x < z or y < w".

(a) Prove this statement with a direct proof.

(b) Prove this statement via contraposition.

3   Fibonacci Proof

Let Fi be the ith Fibonacci number, defined by Fi+2= Fi+1 + Fi and F0 = 0, F1 = 1. Prove that

n

8 Fi2 = FnFn+1 .

i=0

4   Airport

Suppose that there are 2n + 1 airports where n is a positive integer. The distances between any two airports are all different. For each airport, exactly one airplane departs from it and is destined for the closest airport. Prove by induction that there is an airport which has no airplanes destined for it.

5   Coloring Trees

Prove that all trees with at least 2 vertices are bipartite: the vertices can be partitioned into two groups so that every edge goes between the two groups.

[Hint: Use induction on the number of vertices.]

6   Planarity

(a) Prove that K3,3 is nonplanar.

(b) Consider graphs with the property T : For every three distinct vertices v1 , v2 , v3  of graph G, there are at least two edges among them. Use a proof by contradiction to show that if G is a graph on > 7 vertices, and G has property T , then G is nonplanar.

7   Bipartite Graphs

An undirected graph is bipartite if its vertices can be partitioned into two disjoint sets L, R such that each edge connects a vertex in L to a vertex in R (so there does not exist an edge that connects two vertices in L or two vertices in R).

(a) Suppose that a graph G is bipartite, with L and R being a bipartite partition of the vertices. Prove that 8 deg(v) = 8 deg(v).

veL                       veR

(b) Suppose that a graph G is bipartite, with L and R being a bipartite partition of the vertices. Let s and t denote the average degree of vertices in L and R respectively. Prove that s/t = IRI/ILI.

(c) Prove that a graph is bipartite if and only if it can be 2-colored.  (A graph can be 2-colored if every vertex can be assigned one of two colors such that no two adjacent vertices have the same color).

8   Build-Up Error?

What is wrong with the following "proof"? In addition to finding a counterexample, you should explain what is fundamentally wrong with this approach, and why it demonstrates the danger of build-up error.

False Claim: If every vertex in an undirected graph has degree at least 1, then the graph is con- nected.

Proof: We use induction on the number of vertices n > 1.

Base case: There is only one graph with a single vertex and it has degree 0. Therefore, the base case is vacuously true, since the if-part is false.

Inductive hypothesis: Assume the claim is true for some n > 1.