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 = G_{1} (do this first) and G_{2}, G_{4}.

Also, read to page 8 in the textbook.

Due Fri. 1/23:

#A3 (again, do G_{1} first).

Hand in Fri. 1/23:

##A1, A2, A4 for G_{3}.

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

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 = G_{1}, G_{2}, G_{3}. (Omit G_{4}.)

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?