Homework Assignment

CS 171
Homework Assignment 11w
Given: April 09, 2008 Due: April 14, 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. Let G be a graph with n 2 vertices. Prove that if δ(G) n2 , then G is connected.
2. Let k be the maximum length of a path in a connected graph G. If P, Q are paths of
length
k in G, prove that P and Q have a common vertex.
3. Prove that a connected graph with n vertices has exactly one cycle if and only if it has
exactly
n edges.
4. Let G be a graph in which every vertex has degree at least k, where k is an integer at
least 2. Prove that
G has a path of length at least k and a cycle of length at least k + 1.
5. Let G be a connected graph in which every vertex has even degree. Prove that G has
no edge whose deletion leaves a disconnected graph.