Induction Hypothesis

CS 171
Homework Assignment 11m
Given: April 07, 2008 Due: April 09, 2008
This assignment is due by the end of the class on the due date. Unless all problems
carry equal weight, the point value of each problem is shown in [ ]. To receive full credit all
your answers should be carefully justified. Each solution must be the student’s own work.
Assistance should be sought or accepted only from the course staff. Any violation of this
rule will be dealt with harshly.
1. What is wrong with the following “proof” by induction?
Theorem:” For every nonnegative integer n, 5n = 0.
Base Case: 5
· 0 = 0.
Induction Hypothesis: Assume that 5
j = 0 for all nonnegative integers j, 0 j k.
Induction Step: We want to prove the claim for
n = k + 1. Write k + 1 = i + j, where i
and j are nonnegative integers less than k + 1. By the induction hypothesis, 5(k + 1) =
i + j) = 5i + 5j = 0 + 0 = 0.
2. An r-regular graph is a graph in which the degree of each vertex is exactly r. Derive
a simple algebraic relation between
r, n, and m.
3. The complement of a graph G is a new graph formed by removing all the edges of G
and replacing them by all possible edges that are not in G. Formally, consider a graph
G = (V, E). Then, the complement of the graph G is the graph G = (V,E), where
E = {{x, y} |x 6= y,{x, y} 6∈ E}
Prove that for any graph G, G or G (or both) must be connected.