QC > Math > chanusa > 634 > Homework Syllabus • Notes • Topics • Schedule • Homework • 634  
Homework Assignments
Graph Theory – Fall 2009
NOTE! Refresh your browser to get updates!
Exam 2 Practice (Not to be turned in)
  • Midterm: Tuesday, December 15, 2009, 4-6pm
  • The midterm covers everything since the first exam, including Sections 2.3, 3.1, 7.2, 8.1, 8.2, and 8.3, knights tours, de Bruijn sequences, matchings, stable marriages, Kuratowski's theorem, max flow/min cut, transshipments, and dynamic networks. (See notes and topics.)
  • In preparation for the exam, I have compiled some practice problems.
    • 2.3.12, 2.4.4, 2.4.5
    • Q1.  Prove or disprove: the line graph of a Hamiltonian graph is Hamiltonian.
    • Q2.  Use an argument involving girth to prove that the Petersen graph is not planar.
    • Q3.  Find a graph that has two non-isomorphic planar duals. [Hint: Look for different planar embeddings.]
    • Q4.  (hard!) Prove that the Gale-Shapley algorithm is female-pessimal when run with the men proposing.
    • Q5.  Run the Gale-Shapley algorithm with the following sets of preferences with the women proposing:
      Women's Preferences
      AprilBettieCarolDelphiEve
      1st ChoiceFFGGH
      2nd ChoiceGHIHF
      3rd ChoiceIIFJI
      4th ChoiceJGHIG
      5th ChoiceHJJFJ
       
      Men's Preferences
      FreddieGregHaroldIsaacJoe
      1st ChoiceCEAEB
      2nd ChoiceBBDCD
      3rd ChoiceECBAA
      4th ChoiceAAEBC
      5th ChoiceDDCDE
    • Q6.  Practice network flow on this network.
    • Q7.  In Problem 10-3, give two different schedules that show that this amount of commodity can be shipped from A to D in five days or show that there can not possibly be two different shipping schedules.
    • Q8.  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.
    • Q9.  (hard!) It is possible to use max flow/min cut to determine a vertex cover in a bipartite graph. (A vertex cover is a set of vertices that is adjacent to every edge in the graph.) Given a bipartite graph G with bipartition V=X union Y, set up a network like we did in class: create a super-source s that is adjacent to all vertices in X; then create a super-sink t that is adjacent from all vertices in Y. Next, assign capacities to all edges: for the edges you added, give them capacity 1; for the edges of the original graph, give them capacity infinity. Now run the Ford-Fulkerson algorithm on this graph to determine a max flow x* and min cut S*. The set of vertices S* contains some vertices V of X and some vertices W of Y. Prove that the set [(X\V) union W] is a vertex cover of G. [Note: you will need to show that every edge in G is adjacent to some vertex in this set.]
  • You should also go over your past homework problems.
  • If you haven't done it yet, please fill out the online course evaluation. This will help me improve my teaching. I especially appreciate thoughtful comments left in the short answer part of the survey. The deadline for submitting your evaluation online is December 11th. I will not have access to your comments until January, long after your grades are submitted, so feel free to be honest.
Homework 10
To be prepared for discussion on Tuesday, December 8, 2009
  • Please fill out the online course evaluation. This will help me improve my teaching. I especially appreciate thoughtful comments left in the short answer part of the survey. The deadline for submitting your evaluation online is December 11th. I will not have access to your comments until January, long after your grades are submitted, so feel free to be honest.
  • Read the max flow / min cut notes. Then answer the following questions:
    • 10-1.  A spanning tree T in a connected graph G is a subgraph of G that is a tree and includes every vertex of G. (See also p.20 and Section 7.1 in the book.) 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.
    • 10-2.  (a) 7.2.1 and (b) 7.2.3
    • 10-3.  With four men and four women, find sets of preferences for the men and women such that running the Gale-Shapley algorithm with the men proposing and then with the women proposing gives two different sets of marriages. Illustrate how your answers agree with the optimality/pessimality of the algorithm.
    • 10-4.  (a) List all st-cuts in the network pictured below (there are eight). Find the capacity of each cut and determine the min cut.
                (b) Find a maximum flow for the network and show that the max flow / min cut theorem holds.
    • 10-5.  Find the max flow and min cut in this network: (PDF)
    • 10-6.  On the dynamic version of a network from class, use the method of max flow / min cut to determine the maximum amount of the commodity that can be shipped from Warehouse A to Warehouse D in five days. [Assume there is infinite storage of a commodity at every warehouse.] What is a schedule of shipments that transports this maximum amount of commodity from A to D? [Include when shipments leave and their origins and destinations.]
Final Project
Due through Blackboard on Thursday, December 3, 2009
  • A final version of your project is due Tuesday, November 24. Make sure to bring in two paper copies to class for peer review day.
  • Armed with the feedback on your project, revise your project and turn it in by Thursday, December 3 via Blackboard.
Homework 9
To be turned in on Thursday, November 17, 2009
  • Read pp. 179–180 and Section 7.2.
    • 9-1.  Find and prove an "Euler's formula" for disconnected planar graphs.
    • 9-2.  This question has to do with planar duality:
      (a) Show that for all n, the wheel graph Wn is self-dual.
      (b) Show that the planar dual of the octohedron is the cube and vice versa.
    • 9-3.  Prove that the graph G in Figure 9.1.18 (p. 189) is non-planar using two methods:
      (a) Find a subdivision of K3,3 or K5 that is a subgraph of G.
      (b) Through a series of edge deletions and edge contractions, show that either K3,3 or K5 is a minor of G.
    • 9-4.  Show that the Petersen graph is a minor of the graph from Midterm Practice Problem P2.
    • 9-5.  Use the Hungarian algorithm to solve problem 7.2.2.
              Important: Use the initial matching (a,4); (c,6); (e,2); (h,5).
  • Also to keep in mind: Your final version of your project is due Tuesday, November 24. Make sure to bring in two paper copies to class for peer review day.
Homework 8
To be prepared for discussion on Thursday, November 12, 2009
  • Read Sections 3.1, 8.1, 8.2, 8.3, and lecture notes on de Bruijn sequences. Then answer the following questions:
    • 8-1.  3.2.8.
    • 8-2.  Draw the binary de Bruijn graph of order n=5. Find one binary de Bruijn sequence of order 5. [Note: The graph will have 16 vertices and the sequence will be of length 32.]
    • 8-3.  Definition: The line graph L(G) of a graph G has a vertex ve for every edge e of G, and has an edge between any two vertices ve and vf if e and f are adjacent edges of G.
      (a) Let G be a graph with an Eulerian circuit. Prove or disprove: L(G) contains an Eulerian circuit
      (b) Let G be a graph with an Eulerian circuit. Prove or disprove: L(G) contains a Hamiltonian cycle.
    • 8-4.  8.1.9abc [In part (c), add edges---do not subtract them.]
    • 8-5.  (a) 8.2.3 and (b) 8.2.4
    • 8-6.  Show that the Petersen graph is a minor of the graph from Midterm Practice Problem P2.
    • 8-7.  Try to prove the Four Color Theorem by emulating the argument from class using Kempe Chains. What goes wrong?
    • 8-8. (Bonus)  Play the planarity game. Complete levels 1-4 for two bonus points and complete levels 1-7 for two more (four total). If possible, print out the level you complete and your score and turn it in on Thursday.
Homework 7
To be turned in on Thursday, November 5, 2009
  • If you are registered to vote, vote on Tuesday, November 3, 2009. Otherwise, register to vote!
  • Read Sections 2.3, 2.4, and lecture notes on knight's tours. Then write up complete solutions to the following questions:
    • 7-1.  2.3.22. Prove your claim.
    • 7-2.  Figure 2.3.5 is on page 40 of the book.
              (a) Prove that Figure 2.3.5 has no Hamiltonian cycle.
              (b) Show that Figure 2.3.5 has a Hamiltonian path.
    • 7-3.  Determine how many different Hamiltonian cycles there are in (a) Kn. (b) Wn.
      [Assume the vertices are labeled; two Hamiltonian cycles are different if they use different edges.]
    • 7-4.  (a) Prove that there is no closed knight's tour on the 3x8 grid without citing the theorem from class.
              (b) Find a closed knight's tour for the 5x6 grid.
    • 7-5.  (a) Find a graph E which has an Eulerian circuit but no Hamilton cycle.
              (b) Find a graph H which has a Hamilton cycle but no Eulerian circuit.
      [If either is impossible, prove why you can not find such a graph.]
  • You may have fun practicing trying to complete a closed knight's tour
  • Also to keep in mind: Your project outline is due Tuesday, November 10.
Midterm Practice (Not to be turned in)
  • Midterm: Thursday, October 22, 2008
  • Extra Office Hours: Tuesday 10/20 after class, and Wednesday 10/21 3:00-4:00-5:00pm in Kiely 409.
  • I ask that you post a question (and/or a response) on the discussion board for Tuesday 10/20's class. [Not required, but suggested.]
  • The midterm covers Sections 1.1–1.3, 2.1–2.2, connectivity, and graph statistics. (See notes and topics.)
  • In preparation for the midterm, I have compiled some practice problems.
    • 2.1.3, 2.1.4, 2.1.6, 2.2.3, 2.2.5, 3.2.8
    • P1.  Prove that at a party with 49 people, there is always a person who knows an even number of others. [Assume acquaintence is mutual.]
    • P2.  Determine and prove the edge chromatic number for this graph:
    • P3.  For some k greater than or equal to 2, find a k-regular graph that has a bridge.
    • P4.  Show that the Petersen graph P is 3-connected, and determine its edge connectivity.
  • You should also go over your past homework problems.
  • Also to keep in mind: Your project topic is due Tuesday, October 27.
Homework 6
To be prepared for presentation on Thursday, October 15, 2009
  • Read Sections 2.1–2.2. Then complete the following problems.
    • 6-1. Determine the independence number and exhibit an independent set of that size for each of the following graphs: Tetrahedron, Cube, Octahedron, Icosahedron, Dodecahedron. [You should explain why there is no larger independent set.]
    • 6-2.  2.1.16
    • 6-3.  (a) Prove or disprove: If H is a subgraph of G, then κ(H)≤κ(G)
              (b) Prove or disprove: If H is a subgraph of G, then χ'(H)≤χ'(G).
    • 6-4.  Determine χ(Wn). For which n is Wn critical?
    • 6-5.  Is Figure 2.1.5 critical? Justify. (Don't believe everything you read!)
    • 6-6.  Determine the chromatic number and edge chromatic number of the Sierpinski Graph of order n. Prove your result by induction.
    • 6-7.  Consider the (highly!) infinite graph G=(V,E) where V consists of every point in the 2D plane and there is an edge between any two vertices distance 1 unit apart. [For example, vertex (0,0) is connected by an edge to infinitely many points!: those on the unit circle.] Show that the chromatic number of this graph is at least 4. [The exact chromatic number is unknown; it is either 4, 5, 6, or 7.]
Homework 5
To be turned in on Thursday, October 8, 2009
  • Read the notes on connectivity and graph statistics. Then, complete the following problems.
    • 5-1.  Describe the most general 2-regular graph. Prove that all 2-regular graphs fit your description.
    • 5-2.  (a) Prove or disprove: Every 3-connected graph has no bridge.
              (b) Prove or disprove: Every 3-edge-connected graph has no cut vertex.
    • 5-3.  Suppose that P and Q are two maximum paths in a connected graph G. [That is, there is no longer path in G.] Prove that P and Q share a common vertex. [Compare this with Question 4-5(a).]
    • 5-4.  Determine the girth and the diameter of the following graphs: Kn, Km,n, Petersen, Dodecahedron, 5D-cube. Justify your answers and make sure to account for initial cases if they are different.
    • 5-5.  Menger's Theorem says that if the connectivity of a graph is k, then there always exist k edge-disjoint paths between any two vertices u and v. For the two graphs below, prove what κ(G) is for each graph and find the corresponding number of edge-disjoint paths between the vertices labeled u and v. [You may draw the graph and highlight the paths in different colors.]
Homework 4
To be prepared for presentation on Thursday, October 1, 2009
  • Read Section 1.3 and the notes on connectivity. Then complete the following problems.
    • 4-1.  1.3.2 [Prove you are correct.]
    • 4-2.  Exploration Question related to Problem 4-1: 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?
    • 4-3.  1.3.4 (Remember to justify your claim!)
    • 4-4.  Find a minimum disconnecting set and a minimum separating set for each of the following graphs. (Remember to justify!) What is the connectivity and edge connectivity for each graph?
    • 4-5.  Two problems related to the difference between al and um:
              (a) Suppose that P and Q are two maximal paths in a connected graph G. [That is, neither is contained in any larger path in G.] Show that P and Q might not share a common vertex.
              (b) Find an example of a minimal separating set that is not a minimum separating set.
    • 4-6.  What is the minimum number of edges a k-connected graph with n vertices might have?
    • 4-7.  Sudoku is sooo 2008! 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
Homework 3
To be turned in on Tuesday, September 22, 2009
  • Read Section 1.3. Then complete the following problems.
    • 3-1.  Explore the proof of Theorem 1.1.2: The graph below has degree sequence (S1) 4 4 3 3 3 2 2 2 2 1.
      Define (S2) to be 3 2 2 2 2 2 2 2 1. Walk through the steps of the proof of Theorem 1.1.2 in the following way.
      • Let us choose vertex c from the graph to be vertex S from the proof. Determine which of the remaining vertices (a – j) are the vertices Ti and Di from the proof.
      • If you delete vertex S, does the new graph have degree sequence (S2)?
      • Use the method in the proof to modify the graph to be such that removing S gives a graph with degree sequence (S2).
    • 3-2.  Give two examples of self-complementary graphs with more than 4 vertices. (n≥5) Justify that they are self-complementary. Exploration: Write a few sentences about what you can say in general about graphs that are self-complementary.
    • 3-3.  Prove Lemma B (from class on Tuesday, September 15).
    • 3-4.  (a) 1.3.1 [Note: Prove your answer for any tree T satisfying the given condition.]
              (b) 1.3.12
    • 3-5.  We know that in a tree with n vertices, the number of edges is n-1. Prove or disprove: Any graph with n vertices that has fewer than n-1 edges is a forest.
  • Please reference the people you worked with on your homework. (Acknowledgments are nice for everyone!)
Homework 2
To be prepared for discussion on Thursday, September 10, 2009
  • Read Section 1.2. Then complete the following problems.
    • 2-1.  1.1.4. If you determine that the sequence is graphic, draw a graph with the given degree sequence. If you determine that the sequence is not graphic, prove it.
    • 2-2.  1.1.7
    • 2-3.  1.2.5
    • 2-4.  1.2.10 (The conclusion of your argument should be that three graphs are isomorphic to each other.)
    • 2-5.  (a) If G is a k-regular graph, what can you say about Gc? [All vertices have degree k.]
              (b) If G is a connected graph, what can you say about Gc?
    • 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 Thursday, September 10 from 12:15-1:05. Scott Wilson will be giving a talk about algebraic topology that should be very understandable. Please join us!
Homework 1
To be turned in on Thursday, September 3, 2009
  • 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.
  • You will need to print the next set of notes for Thursday's class.
  • Read Section 1.1. Chapter 1 scanned here. (pdf, 5 MB) Then complete the following problems.
    • 1-1.  (Complete online before class Thursday for credit.)
      (a) Email me at chanusa@qc.cuny.edu with the email address where you are best contacted. (Make sure to include your name in the message as well!)
      (b) Go to the class Discussion Board. Introduce yourself on the "Class Introductions" thread.
    Problems 1-2 through 1-5 should be written up and handed in on Thursday:
    • 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.) Explain what in your example corresponds to the abstract concepts of vertices, edges, and vertex degree.
    • 1-3.  1.1.1
    • 1-4.  1.1.2ab, both without using Theorem 1.1.2. If you determine that the sequence is graphic, draw a representative graph with the given degree sequence.
    • 1-5.  1.1.5
  • 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.

Back to the Graph Theory Home Page.
Christopher Hanusa – Queens College – Mathematics Department.