Scroll down for Homework 5.

• Exam 2: Wednesday, May 9, 2012 (This is two days later than originally scheduled.)
• The Question and Answer session will be held on Monday, May 7, 2012.
• The midterm covers planarity and algorithms, including but not limited to Sections 7.1, 7.2, 8.1, 8.2, 8.3, 9.1, 9.2, and 10.3. (See course notes for our daily topics.)
• In preparation for the midterm, I have compiled some practice problems.
  • 7.1.1, 7.1.10, 7.2.1, 7.2.3, 8.1.15, 8.3.7, 9.1.4, 9.1.8,
  • Q-1.  Find and prove an "Euler's formula" for disconnected planar graphs.
  • Q-1.  Find a graph that has two non-isomorphic planar duals. [Hint: Look for different planar embeddings.]
  • Q-2.  Prove that if all the edge costs are different, then there is only one minimum-weight spanning tree.
  • Q-3.  The market for kumquats is booming!
    Five markets (I through V) each have put orders into the five large kumquat distributors (A through E).
    A has 5 kumquats and can deliver to I, II, and III.
    B has 4 kumquats and can deliver to I, III, and IV.
    C has 2 kumquats and can deliver to II and III.
    D has 5 kumquats and can deliver to III and V.
    E has 4 kumquats and can deliver to IV and V.
    Market I desires 5 kumquats, II desires 2, III desires 4, IV desires 6, and V desires 3.
         Is it possible for all the markets to receive their desired quantity of kumquats for the distributors? If so, give a valid transshipment. If not, explain why not.
  • Q-4.  Use the Ford-Fulkerson algorithm to find the max flow and min cut in this network: (PDF)
  • Q-5.  Prove the correctness of the following algorithm, which finds a spanning tree of a graph. [Remember: Prove that the algorithm terminates and that the output of the algorithm is a spanning tree of G.]
    Input: A graph G with n vertices.
    Preprocess: Label the vertices 1 through n, color them all white. Let T be a set of edges, initially empty.
    Repeat: For the lowest numbered white vertex v, order the edges incident with v. Going through each edge e from first to last, determine if including e in T would create a cycle in T. If it would not create a cycle, place e into T (T is growing.) If it would create a cycle, do not add e to T; go on to the next edge. Once every incident edge to v has been checked, color v black. If all vertices are black, go on to the next step. Otherwise, repeat this step.
    Output: Output the graph T, a spanning tree of G.
• You should also go over your past homework problems.
• For informational purposes only, here is a copy of a second exam from the past. No guarantees of similarity are assured.

• Reminder: Peer review day on Monday, April 23; bring in two paper copies of your paper.
• Reminder: Revise your paper to turn it in on Monday, April 30.
• For Wednesday, May 2, read Section 7.1 and our notes on algorithms. Then complete the following four problems, each worth five points each.
  • 5-1.  Use the Hungarian algorithm to solve problem 7.2.2.
            Important: Use the initial matching (a,4); (c,6); (e,2); (h,5).
  • 5-2.  Run the Gale-Shapley algorithm twice on the following sets of preferences, once with the men proposing, and once with the women proposing. Discuss how your results are related to the theorems on optimality and pessimality.

    Women's Preferences
    	Angela	Bettie	Carol	Delphi	Eve
    1st Choice	F	F	G	G	H
    2nd Choice	G	H	I	H	F
    3rd Choice	I	I	F	J	I
    4th Choice	J	G	H	I	G
    5th Choice	H	J	J	F	J

     

    Men's Preferences
    	Filipe	Greg	Harold	Isaac	Joe
    1st Choice	C	E	A	E	B
    2nd Choice	B	B	D	C	D
    3rd Choice	E	C	B	A	A
    4th Choice	A	A	E	B	C
    5th Choice	D	D	C	D	E

  • 5-3.  (a) List all st-cuts in the network pictured below (there are eight). Find the capacity of each st-cut and determine the min cut from this information.
            (b) Find a maximum flow for the network (and verify that it is a max flow). Then verify that the max flow / min cut theorem holds. [It is not required to use the Ford-Fulkerson algorithm in this problem.]
    
  • 5-4.  Use the Ford-Fulkerson algorithm to find the max flow and min cut in this network: (PDF)

• Read Sections 8.1, 8.2, 9.1 through p184, 9.2 through top p192, and look at the pictures in Section 10.3. Then complete the following problems.
  • 4-1.  Use an argument involving girth to prove that the Petersen graph is not planar.
  • 4-2.  Why doesn't the Kempe Chains argument work to prove the Four Color Theorem?
  • 4-3.  Show that the Petersen graph is a minor of the graph from Midterm Practice Problem P-2.
  • 4-4.  Prove that the graph G in Figure 9.1.18 (p. 189) is non-planar using two methods:
    (a) Find a subdivision of K_3,3 or K₅ that is a subgraph of G.
    (b) Through a series of edge deletions and edge contractions, show that either K_3,3 or K₅ is a minor of G. Find two graphs with the same degree sequence, one of which is a tree and one of which is not.
  • 4-5.  9.1.7
  • 4-6.  9.2.2
  • 4-7.  Sudoku is sooo last decade! Solve this Hashi puzzle. Instructions: Edges connecting the circles (vertices) must be either vertical or horizontal. Up to two edges may be drawn connecting the same circles. The edges drawn may not cross, and the degree of each vertex is the enclosed number. Also, the entire graph must be connected!
           For many more Hashi puzzles and other fun games, visit Hashi puzzles or Puzzle Bridges
  • Bonus.  Play the planarity game (See also: http://www.planarity.net/).
    Complete levels 1-4 for two bonus points and complete levels 1-7 for two more (four total). If possible, print out the last level you completed with your score and turn it in on Wednesday.
• I will be giving a department colloquium on Wednesday, April 4 from 12:15-1:05 in Kiely 242. You are welcome to join us!

• Exam 1: Wednesday, March 14, 2012
• The midterm covers Sections 1.1–1.3, 2.1–2.2, connectivity, and graph statistics. (See course notes for our daily topics.)
• In preparation for the midterm, I have compiled some practice problems.
  • 1.3.2, 2.1.3, 2.1.4, 2.1.6, 2.2.3, 2.2.5
  • Practice the remaining graph statistics from the group worksheet. (Check your answers against the answers to the boxed questions.)
  • P-1.  Prove that at a party with 49 people, there is always a person who knows an even number of others. [Assume acquaintence is mutual.]
  • P-2.  Determine and prove the edge chromatic number for this graph:
    
  • P-3.  For some k greater than or equal to 2, find a k-regular graph that has a bridge.
  • P-4.  (a) If G is a k-regular graph, what can you say about G^c? [All vertices have degree k.]
            (b) If G is a connected graph, what can you say about G^c?
  • P-5.  Is Figure 2.1.5 critical? Justify. (Don't believe everything you read!)
  • P-6.  Exploration question: Let G have n vertices and n edges. If G has more than one connected component, what can we say about the number of cycles in the graph? Can you determine a formula?
• You should also go over your past homework problems.
• For informational purposes only, here is a copy of a first exam from the past. No guarantees of similarity are assured.
• Also to keep in mind: Email Prof. Chris your project topic by Friday, March 16.

• Read Section 1.3 and our notes on graph statistics. Then complete the following problems.
  • 3-1.  Determine, with proof, the vertex connectivity, edge connectivity, clique number, and independence number of each of the graphs below. (You can ignore the loop in Graph $G_4$ if it bothers you.)
  • 3-2.  Suppose that $P$ and $Q$ are two maximum paths in a connected graph $G$. Prove that $P$ and $Q$ share a common vertex.
  • 3-3.  (a) Suppose that $P$ and $Q$ are two maximal paths in a connected graph $G$. Show that $P$ and $Q$ might not share a common vertex.
            (b) In a graph with vertex connectivity at least two, find an example of a minimal cut set that is not a minimum cut set.
  • 3-4.  (a) 1.3.1 [Note: Prove your answer for any tree T satisfying the given condition.]
            (b) 1.3.20
  • 3-5.  Determine the girth and the diameter of the following graphs: $K_n$, $K_{m,n}$, Petersen, Dodecahedron, 5D-cube. Justify your answers and make sure to account for initial cases if they are different.
• Please reference the people you worked with on your homework. (Acknowledgments are nice for everyone!)

• Read Sections 1.2 and 1.3 and the course notes on connectivity. Then complete the following problems.
  • 2-1.  1.1.7
  • 2-2.  Find two graphs with the same degree sequence, one of which is a tree and one of which is not.
  • 2-3.  1.2.4 and 1.2.5.
  • 2-4.  Prove Lemma B. Prove Lemma A.
  • 2-5.  1.2.8
  • 2-6.  Draw the Schlegel diagram for two of the following polyhedra: Icosidodecahedron, Truncated Icosahedron, Rhombicuboctahedron, Snub Cube. (You will have to do some investigating to determine what these polyhedra are.)
• The first department colloquium is scheduled for Wednesday, February 15 from 12:15-1:05, presented by Prof. Krzysztof Klosin. You are welcome to join us!

• Thoroughly read the class web page including the syllabus, schedule, and letters from past students. This should answer all the questions that you may have about the class.
• Don't forget to print out the next set of notes for Wednesday's class.
• Read Section 1.1 in the textbook. Chapter 1 scanned here. (pdf, 5 MB) Then complete the following problems.
• Problem 1-1 must be completed online before class on Monday 2/6 Wednesday 2/8 for credit.
  • 1-1.  (a) Email me at chanusa@qc.cuny.edu with the email address where you are best contacted. (Make sure to include your name and "Math 634" in the message as well!)
            (b) Take the syllabus quiz on Blackboard. Retake the quiz as necessary to earn a score of 100%.
• Problems 1-2 through 1-5 should be written up and handed in on Wednesday:
  • 1-2.  Write a paragraph or two giving an example of where you have seen graphs in real life. (Do not use the examples from class unless you have a unique perspective.) In your example, explain what corresponds to the abstract concepts of vertices, edges, and vertex degree, and discuss whether a vertex can have a degree of zero or one.
  • 1-3.  1.1.1 [If you intend to use graph theory, explain why you can.]
  • 1-4.  1.1.2ab, both without using Theorem 1.1.2. [Hint: You will need to find a family of graphs, one for every n.]
  • 1-5.  1.1.5 [Remember: "Show" means "Prove"]
• Remember what is expected:
  • When the problem says "Find a graph with property A", you need to draw the graph and explain why the graph has the property you claim it does.
  • When the problem says "Prove X" or "Show X", you need to give a rigorous mathematical argument explaining why "X" is true.
  • It may be the case that an example or a counterexample of a graph is the key to your rigorous mathematical proof. If this is the case, you will need to explain why you have drawn it and what purpose it serves.
  • Write in full sentences.
  • Follow the guidelines for turning in homework.