Homework Set I (1/24)

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

Due Tues., 1/25:
Do for discussion: ## A1, A2, A4 for G = G₁ (do this first) and G₂, G₄.
Also, read to the middle of page 9 (changed) in the textbook.
Also, read the course information page and the homework instructions.

Due Wed. 1/26:
Do for discussion: # A3 (again, do G₁ first).

Hand in Wed. 1/26:
## A1–A4 for G₃.

Problem Set A

Some terminology about a graph (from the announcements page):

• 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 edges 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₁, G₂, G₃. (Omit G₄.)

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?