*Varied due dates.*

- 4#1 Due Thursday, October 10: (Related to West 1.3.23) As West describes
in the last paragraph of Example 1.3.8, the
`k`-dimensional hypercube,`Q`, can be defined recursively as follows:_{k}`Q`is a single vertex._{0}`Q`is constructed from two copies of_{k}`Q`; the two copies are stapled together by connecting like vertices._{k-1}Use the recursive description of

`Q`to prove by induction that_{k}`n(Q`. Then, prove by induction that_{k}) = 2^{k}`e(Q`._{k}) = k2^{k-1} - 4#2 Due Friday, October 11: (West 1.3.8)
- 4#3 Due Monday, October 14: Write up the solution to the
in-class exercise (West 1.3.10). This requires three steps
- State the conditions.
- Prove they are necessary, i.e., if a graph has
`m`odd-degree vertices and`l`even degree vertices, then`m`and`n`satisfy your conditions. - Prove they are sufficient. If
`m`and`n`satisfy your conditions, then there is a graph with`m`odd-degree vertices and`l`even-degree vertices.

- 4#4 Due Tuesday, October 15: Prove, by top-down induction (as in
Friday's course handout), that every triangulation of an
`n`-sided polygon yields`n-2`triangles. - 4#5 Due Thursday, October 17: In groups of
up to three students, come up with three specific applications of
graph theory. One should be in computer science, one in the sciences,
and one outside of the sciences. For each application,
- Describe the application in words.
- Specify what the vertices and edges of the graph would be. (If you wish, the vertices or edges of the graph could have weights; if so, specify the weights.)
- State any properties a typical graph might have. Is it directed or undirected? Is it cyclic or acyclic? Would it be bipartite?
- State a question about the graph that would be relevant to the application. Phrase the question twice, once in terms of the application, and once (as best you can) in terms of graph theory.

`A`to airport`B`if there is a scheduled flight from`A`to`B`. The graph would be directed, since it's conceivable that there's a flight from`A`to`B`but not from`B`to`A`. Add edges weights which are the air distances of the flights. An interesting question is, "What is the shortest distance I have to travel in the air to fly from airport`u`to airport`v`?" In graph theory terms, what is the shortest`uv`-path in the graph, where distance is measure by the edge weights?