MCS-236 Homework 4

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_k, can be defined recursively as follows: Q₀ is a single vertex. Q_k is constructed from two copies of Q_k-1; the two copies are stapled together by connecting like vertices.

  Use the recursive description of Q_k to prove by induction that n(Q_k) = 2^k. Then, prove by induction that 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
  1. State the conditions.
  2. 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.
  3. 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.
  As a sample application outside of the sciences, consider airline schedules. The vertices are aiports. There is an edge from airport 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?