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 |
| April | 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 |
| Freddie | 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 |
- 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.
|