1. Prove that it is impossible to have a group of nine people ata party such that each one knows exactly five others in thegroup.
2. Let G be a graph with n vertices, t of which have degree k andthe others have degree k+1. Prove that t = (k+1)n - 2e, where e isthe number of edges in G.
3. Let G be a k-regular graph, where k is an odd number. Prove thatthe number of edges in G is a multiple of k.
4. Let G be a graph with n vertices and exactly n-1 edges. Provethat G has either a vertex of degree 1 or an isolated vertex.
5. Show that the k-cube has 2^k vertices and k2^(k-1) edges and isbipartite.
6. Prove that if G is a simple graph with at least two vertices,then G has two or more vertices of the same degree.