BU > Math > chanusa > 381 > Homework Syllabus • Topics • Schedule • Homework • 381  
Homework
Graph Theory – Spring 2008
NOTE! Refresh your browser to get updates!
Homework 15S
Special Practice Homework
  • Exam 3: Monday, May 12, 2008 from 4:30-6:30pm in FA 212
  • Extra Office Hours: Monday, May 12, 1-2:30pm
  • In preparation for the third exam, I have compiled some practice problems.
    • Try examples of all the algorithms we did in class.
    • 7.2.3, 8.1.4, 8.1.14, 8.2.3, 8.2.5, 8.3.2, 8.3.7, 9.1.4, 9.1.5, 9.1.7, 9.1.9, 9.1.10
    • 15S1. Prove that the Petersen graph is not planar without using Kuratowski's Theorem. [Hint: use an argument involving its girth.]
    • 15S2. Show that the Petersen graph is a minor of the graph from Homework 7B.
    • 15S3. Find an ``Euler's formula'' for disconnected graphs.
    • 15S4. For each of the graphs in your table of statistics, find its crossing number, thickness, genus, incidence matrix, adjacency matrix, eigenvalues, etc. .
    • 15S5. Let G be a directed graph with a directed cycle. What can you say about the entries of the infinite matrix sum I+A1+A2+A3+A4+...? Is this sum equal to (I-A)-1 in this case? Why or why not?
  • You should also go over your past homework problems.
Homework 14B (Optional)
Friday, May 9, 2008
  • This homework is optional. If you are happy with your homework grade this semester, you do not need to turn in this assignment, and this assignment will not be counted as your dropped homework. However, the material covered in this homework is on the third exam, so it may be in your best interest to work hard on this assignment.
    • 14B1.  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. Show that your answers illustrate the optimality/pessimality of the algorithm.
    • 14B2.  Find the max flow and min cut in this network: (PDF)
    • 14B3.  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.
    • 14B4.  It is possible to use max flow/min cut to determine a vertex cover in a bipartite graph. (Remember 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.]
NOW POSTED!!! Copy of the network from Monday's class.
Homework 14A
Tuesday, May 6, 2008
  • [By noon Tuesday] Go to blackboard and post a question about the past week on the discussion board, in the thread labeled Homework 14A. You may also post a reply to another student's post.
    • 14A1.  7.2.1
    • 14A2.  Show that the Hungarian Algorithm does not work for non-bipartite graphs
    • 14A3.  Prove that the Gale-Shapley algorithm is female-pessimal when run with the men proposing.
    • 14A4.  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
    • 14A5.  Complete the max flow/min cut problem from Monday's class.
  • Reminder: Your final project is due on Wednesday the 7th through Blackboard's turnitin feature. Go to the course Blackboard page and click on Assignments. Submit your project electronically from there.
Homework 13B
Friday, May 2, 2008
  • See this page for a Proof of the matrix tree theorem
  • Read this webpage for an application of powers of the adjacency matrix (note that the author calls it incorrectly the incidence matrix).
  • Read Section 7.2 and complete the following problems.
    • 13B1.  (a) Give an interpretation for the existence of lambda=1 and lambda=-1 as eigenvalues for a directed cycle from Problem 12B4. (b) What simple values would you expect for the eigenvalues of an undirected cycle?
    • 13B2.  Let G be the star graph St6 plus an edge. That is, let G be the graph on seven vertices with degree sequence (6,2,2,1,1,1,1). (a) Use the Matrix Tree Theorem to find the number of spanning trees of G. (b) Verify your answer by counting the number of spanning trees by hand.
    • 13B3.  (a) Find the incidence and adjacency matrices for the graph pictured below. (b) Calculate the number of paths walks of length 7 from the upper left corner to the right vertex in the graph using powers of one of the matrices you found in part (a).
    • 13B4.  Use the Hungarian algorithm to solve problem 7.2.2. Use the initial matching a,4; c,6; e,2; h,5.

Tuesday, April 29, 2008
  • There is no homework assignment for Tuesday, April 29. Instead, the final draft of your project is due. Bring in two copies of your draft to share with your classmates. You will give a brief explanation of your project's subject to a group of your peers. After this, you will pass around your drafts and make comments on the other group members' projects. With these comments in hand, you will be able to revise your project for submission via Blackboard on Wednesday, May 7.
Homework 12B
Friday, April 25, 2008
  • Here is a source for matrices used in graph theory: (Bibliographic Info) (Definitions, Theorems, etc.).
  • Read Sections 9.2 (to p193) and 10.3 (to p230), and complete the following problems.
    • 12B1.  9.1.1
    • 12B2.  (a) 9.2.2 [Do not use the formula from the book.] (b) 9.2.4
    • 12B3.  (a) How are the adjacency matrices for an (undirected) graph and its complement related? (b) Find a graph that has the following matrix as its adjacency matrix.
      010001
      101101
      010101
      011001
      000001
      111110
    • 12B4.  (a) Find the adjacency matrix A and characteristic polynomial of a directed cycle Cn=v1->v2->...->vn->v1. (b) For which values of n is lambda=1 an eigenvalue of A? What about lambda=-1? Give an eigenvector of A that corresponds to each of these eigenvalues.
Homework 11A
Tuesday, April 15, 2008
  • [By noon Tuesday] Go to blackboard and post a question about the past week on the discussion board, in the thread labeled Homework 11A. You may also post a reply to another student's post.
  • Read Sections 8.1 and 8.2. Then complete the following exercises.
    • 11A1.  (a) Show that the wheel Wn is self-dual. (b) Find a graph that has two non-isomorphic planar duals. [Look for different planar embeddings.]
    • 11A2.  8.1.5
    • 11A3.  (a) 8.1.7 (b) 8.1.8
    • 11A4.  8.2.4
    • 11A5.  Try to prove the 4 Color Theorem by emulating the argument from class using Kempe Chains. What goes wrong?
    • 11A6.  (a) Find an embedding of K6 on the torus.
      (b) Show that the generalization of Euler's formula holds in this case. (That p-q+r=2-2g.)
    • 11A7.  Play the planarity game.
  • The next homework assignment will be Homework 12B, due Friday, April 25.
Homework 10S
Special Practice Homework (Not to be turned in)
Homework 9B
Friday, April 4, 2008
  • Read Sections 2.3, 2.4, and 3.1. Then complete each of the following questions.
    • 9B1.  (a) 2.3.22 (b) 2.4.20
    • 9B2.  Prove or disprove the line graph of an Eulerian graph is (a) Eulerian and (b) Hamiltonian.
    • 9B3.  (a) Prove that there is no closed knight's tour on the 4x4 grid without citing the theorem from class. (b) Find a closed knight's tour for the 5x6 grid. [For one point, give an open knight's tour.]
    • 9B4.  Draw the de Bruijn graph of order 3 on the alphabet {0,1,2}. Find one de Bruijn sequence of order 3 on {0,1,2}.
  • Exam 2 is on Tuesday, April 8!
Homework 9A
Tuesday, April 1, 2008
  • [By noon Tuesday] Go to blackboard and post a question about the past week on the discussion board, in the thread labeled Homework 9A. You may also post a reply to another student's post.
  • Read sections 2.3, 2.4, and 3.1. Then complete the following exercises.
    • 9A1.  (a) 2.4.2 (b) 2.4.3
    • 9A2.  (a) 2.4.5 (b) 2.4.8
    • 9A3.  2.4.12
    • 9A4.  (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.
    • 9A5.  3.1.5
    • 9A6.  (a) 3.1.7 (b) 3.1.8
  • You may have fun practicing trying to complete a closed knight's tour
Homework 8A
Tuesday, March 18, 2008
  • [By noon Tuesday] Go to blackboard and post a question about the past week on the discussion board, in the thread labeled Homework 8A. You may also post a reply to another student's post.
  • Complete the following exercises.
    • 8A1.  Determine the chromatic number and edge chromatic number of the graph G in the following figure.
    • 8A2.  Find the line graph L(G) of the graph G in Exercise 8A1. Determine the chromatic number of L(G).
    • 8A3.  (a) Find a red-blue coloring of K5 with no monochromatic triangle. (b) Find a red-blue coloring of K8 with no red K3 nor blue K4.
    • 8A4.  Six random points in space are joined pairwise by 15 line segments, where all the segments are of different length. Prove that at least one of the 15 segments serves as the shortest side in one of the triangles it is in, and as the longest side in another. [Hint: Use Ramsey Theory.]
    • 8A5.  2.3.11
    • 8A6.  (a) 2.3.19 (b) 2.3.20
  • The next homework assignment will be Homework 9A, due Tuesday, April 1.

Proof of Stanley's acyclic orientation result
Homework 7B
Friday, March 14, 2008 Final version-Updated March 10, 2008
  • Read Sections 2.2, 4.3, and the first paragraph of Section 2.3. Then complete each of the following questions, each worth 5 points.
    • 7B1.  Is Figure 2.1.5 critical? Justify. (Don't believe everything you read!)
    • 7B2.  Prove that no 3-regular graph (cubic graph) has a decomposition into copies of P5.
    • 7B3.  Determine and prove the edge chromatic number for this graph:
    • 7B4.  (a) 4.3.2 (b) 4.3.3 [Don't forget to justify that your graphs satisfy the desired information.]
Homework 7A
Tuesday, March 11, 2008
  • [By noon Tuesday] Go to blackboard and post a question about the past week on the discussion board, in the thread labeled Homework 7A. You may also post a reply to another student's post.
  • Read Section 2.2. Then complete the following problems.
    • 7A1.  Determine the number of acyclic orientations of the figure from 6B4 (a) by hand (b) using the chromatic polynomial.
    • 7A2.  The chromatic polynomial of the wheel W5 is PG(λ) = λ6 - 10λ5 + 40λ4 - 80λ3 + 79λ2 - 30λ. Determine the chromatic number of W5 (a) by hand (b) using the chromatic polynomial.
    • 7A3.  Show that no perfect matching exists in both halves of Figure 2.2.6
    • 7A4.  2.2.9
    • 7A5.  2.3.1
    • 7A6.  2.3.2
Homework 6B
Friday, March 7, 2008
  • Read Section 2.2. Then complete each of the following questions, each worth 5 points.
    • 6B1.  (a) Find a graph G with 6 vertices and 9 edges such that G has no subgraph isomorphic to K4. (b) Can you add in any more edges to your graph and preserve the property of not containing a K4? [In other words, is your graph maximal?] (c) In all graphs G with 6 vertices, what is the maximum number of edges that G can have and still not contain a K4? Prove it. [This problem inspired by 2.1.15a]
    • 6B2.  Use induction to prove that χ(T) ≤ 2 when T is a tree. [Do not use Theorem 2.1.6.]
    • 6B3.  Let a(G) be equal to the average vertex degree in G. Prove or disprove: χ(G) ≤ 1+ a(G).
    • 6B4.  Find the chromatic polynomial PG(λ) for the following graph by (a) a direct argument (b) Using a deletion-contraction argument.
Homework 6A
Tuesday, March 4, 2008
  • [By noon Tuesday] Go to blackboard and post a question about the past week on the discussion board, in the thread labeled Homework 6A. You may also post a reply to another student's post.
  • Read Section 2.1. Then complete the following problems.
    • 6A1.  2.1.3
    • 6A2.  2.1.4
    • 6A3.  (a) 2.1.6 (b) 2.1.7 (Notice that what is asked for is stronger than a proper coloring.)
    • 6A4.  2.1.24
    • 6A5.  (a) Find more than one example of a critical graph with &chi(G)=2. (b) Find more than one example of a critical graph with &chi(G)=3.
Report Part I
Friday, February 29, 2008
  • No homework is due Friday.
  • The first part of your semester project is due. [Email submission is fine.] If you are an MAT student or future teacher, you need not indicate your topic (although you may if you wish), however please indicate your target audience.
Homework 5S
Special Practice Homework (Not to be turned in)
  • Exam 1: Tuesday, February 26, 2008
  • Extra Office Hours: Tuesday, February 26, 12:00-1:00
  • In preparation for the exam, I have compiled some practice problems. [More may come later. Or not.]
    • 1.3.14, 2.4.7, 2.4.8, 2.4.22
    • 5S1. Suppose T and T' are two different spanning trees of the connected graph G, and let e is an edge in E(T)\E(T'). Prove that there exists an edge e' in E(T')\E(T) E(T)\E(T') such that T'+e-e' and T+e'-e are spanning trees of G
    • 5S2.  Suppose that P and Q are two paths of maximal length in a connected graph G. Show that P and Q may not share a common vertex. [Compare this to question 3B2.]
    • 5S3.  Use the graphs from 4A2 (or create your own!) to find an example of (a) a disconnecting set that is not an edge cut, and (b) an edge cut that is not a minimal disconnecting set.
  • You may post a question (and/or a response) on the discussion board.
  • You should also go over your past homework problems.
Homework 4B
Friday, February 22, 2008
  • This week there are only four questions. Each will be worth 5 points.
  • You may find this compilation of connectivity definitions from class helpful.
    • 4B1. Let G be a 2-connected graph with at least three vertices. Prove that there are two adjacent vertices v and w such that G \ v \ w is still connected. [Hint: Consider a spanning tree.]
    • 4B2.  Use the graphs from 4A2 (or create your own!) to find an example of (a) a minimal disconnecting set that is not a minimum disconnecting set, (b) a minimal separating set that is not a minimum separating set, and (c) a maximal independent set that is not a maximum independent set. [You only need find one example for each.]
    • 4B3.  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.]
    • 4B4. Prove that the block graph of any connected graph is a tree. [Hint: What two things do you have to prove?]
  • Exam 1 is on Tuesday, February 26!
Homework 4A
Tuesday, February 19, 2008
  • [By noon Tuesday] Go to blackboard and post a question about the past week on the discussion board, in the thread labeled Homework 4A. You may also post a reply to another student's post.
  • Read Theorems 2.4.1 and 3.2.1. Then complete the following problems.
    • 4A1.  Show that the wheel graph Wn is 3-connected for all n≥4.
    • 4A2.  Find a cut set and a separating set for each of the following graphs. What is the connectivity and edge connectivity for each graph?
    • 4A3.  For each of the graphs in the previous picture, determine the maximum independent set.
    • 4A4.  For some k greater than or equal to 2, find a k-regular graph that has a bridge.
  • We'll also do presentations on the compiled statistics from class.
Homework 3B
Friday, February 15, 2008
  • Complete the following problems.
    • 3B1.  (a) 2.1.21 (b) 2.1.22a
    • 3B2.  Suppose that P and Q are two paths of maximum length in a connected graph G. Prove that P and Q share a common vertex.
    • 3B3.  Determine the girth and the diameter of the following graphs: Kn, Km,n, Petersen, Dodecahedron, 5D-cube
    • 3B4.  Show that the Petersen graph P is 3-connected, and determine its edge connectivity.
    • 3B5.  (a) Prove or disprove: Every 3-connected graph has no bridge. (b) Prove or disprove: Every 3-edge-connected graph has no cut vertex.
Homework 3A
Tuesday, February 12, 2008
  • [By noon Tuesday] Go to blackboard and post a question about the past week on the discussion board, in the thread labeled Homework 3A. You may also post a reply to another student's post.
  • Read Section 1.3. Then complete the following problems.
    • 3A1.  1.3.11
    • 3A2.  In class we calculated the number of unlabeled trees and labeled trees on 4 vertices. Calculate the number of unlabeled trees and labeled trees on 5 vertices, and verify that Cayley's Theorem holds for n=5.
    • 3A3.  Draw the Schlegel diagram for two of the following polyhedra: Icosidodecahedron, Truncated Icosahedron, Rhombicuboctahedron, Snub Cube.
    • 3A4.  (a) If G is a k-regular graph, what can you say about Gc? (b) If G is a connected graph, what can you say about Gc
    • 3A5.  Give two examples of self-complementary graphs with more than 4 vertices. (n≥5)
    • 3A6.  Sudoku is sooo 2007! 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! (Thanks Jason for pointing out that I needed to clarify that.)
             For many more Hashi puzzles and other fun games, visit Hashi puzzles or Puzzle Bridges
Homework 2B
Friday, February 8, 2008
  • Read Section 1.3. Then complete the following problems.
    • 2B1.  (a) 1.3.1 (b) 1.3.12
    • 2B2.  (a) 1.3.2 (b) 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?
    • 2B3.  1.3.13. Justify your answer.
    • 2B4.  Let G be a graph that has a cycle C, and let e be some edge in the cycle. Remove e from G to create a graph H. Show that if there is a path from vertex v to vertex w in G, there is also a path between these same vertices in H. [Note: Unlike in class, there are no restrictions on G. G may have more than the one cycle; it may even be disconnected.]
    • 2B5. 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 2A
Tuesday, February 5, 2008
  • [By noon Tuesday] Go to blackboard and post a question about the past week on the discussion board, in the thread labeled Homework 2A. You may also post a reply to another student's post.
  • Read Section 1.2 and complete the following problems. Remember, you will be called on randomly to present the solutions at the board.
    • 2A1.  1.2.4
    • 2A2.  1.2.5
    • 2A3.  1.2.8
    • 2A4.  1.2.9
    • 2A5.  Prove that at a party with 49 people, there is always a person who knows an even number of others. [Assume acquaintence is mutual.]
Homework 1B
Friday, February 1, 2008
  • Read Sections 1.1 and 1.2. Then complete the following problems.
    • 1B1.  1.1.2ab, both without using Theorem 1.1.2
    • 1B2.  1.1.4
    • 1B3.  1.1.5
    • 1B4.  1.1.6
    • 1B5.  1.2.4
    • 1B5. 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).
  • 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.
Homework 1A
Tuesday, January 29, 2008
  • Thoroughly read the class web page including the syllabus and schedule. This should answer all the questions that you may have about the class.
  • Go to the class Discussion Board. Introduce yourself on the "Class Introductions" thread. (You need not ask a question on the discussion board this week.)
  • Read Section 1.1 and complete the following problems.
    • 1A1.  1.1.1
    • 1A2.  1.1.10

Back to the Graph Theory Home Page.
To Chris's Math Home Page.
Binghamton University  Department of Mathematical Sciences