1.

a) We say that a graph is d-regular if every vertex has degree d. Is it true that for all n, there exists (2n 2)-regular simple graph on 2n vertices? Describe such graph for each n, or show that no such graph exists for some n. (3pts)

b) Is it true that for all n, there is a simple graph on n vertices with n distinct degrees? Describe such a graph for each n or show that no such graph can exist for some n. (4pts)

c) Is it true that for all n, there is a simple graph on n vertices with n 1 distinct degrees? Describe such graph for each n or show that no such graph can exist for some n. (4pts)

2.

Prove using mathematical induction that if G is a simple connected graph, and has n=|V| edges, then G contains precisely one simple circuit. (5pts)

3.

Let G = (V, E) be a simple graph. For each subset of vertices U, define (U) to be the number of edges in the graph with one endpoint in U and the other in V U. Show that there exists a U with (U) |E|/2. (5pts)