Homework Set I (1/21)

This assignment is for discussion in class (except as called "Hand In"). Come up with ANY IDEAS at all and bring them along!

Due Thurs., 1/22:
##A1, A2, A4 for G = G1 (do this first) and G2, G4.
Also, read to page 8 in the textbook.

Due Fri. 1/23:
#A3 (again, do G1 first).

Hand in Fri. 1/23:
##A1, A2, A4 for G3.

Go to announcements | course information | homework list | next homework.

Problem Set A

Some terminology about a graph:

Order:
the number of vertices.
Size:
the number of edges.
Separating set:
a set of vertices whose removal leaves a disconnected graph.
Disconnecting set:
a set of vertices whose removal leaves a disconnected graph.

A1. (a) Find a separating set.
(b) Find one that is smallest.

A2. (a) Find a disconnecting set.
(b) Find one that is smallest.

A3. Write down the degree sequence of G = G1, G2, G3. (Omit G4.)

A4. Treat G as a graph in which the vertices stand for people and the edges join pairs who don't get along together, so they can't be on the same committee. What is the largest possible committee?

The four graphs.