# Proofs On Graphs Homework Questions

**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.
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.*]
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.
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*W*is self-dual._{n}**(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*K*or_{3,3}*K*that is a subgraph of_{5}*G*.**(b)**Through a series of edge deletions and edge contractions, show that either*K*or_{3,3}*K*is a minor of_{5}*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.
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*v*for every_{e}**edge***e*of*G*, and has an edge between any two vertices*v*and_{e}*v*if_{f}*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-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.
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)***K*._{n}**(b)***W*._{n} [*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: Thursday, October 22, 2008**- Extra Office Hours: Tuesday 10/20 after class, and Wednesday 10/21 3:00-4: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.
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*χ(W*. For which_{n})*n*is*W*critical?_{n}**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.*]
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:*K*,_{n}*K*, Petersen, Dodecahedron, 5D-cube. Justify your answers and make sure to account for initial cases if they are different._{m,n}**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.]
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
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 (*S*) 4 4 3 3 3 2 2 2 2 1._{1} Define (*S*) 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._{2}- 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*T*and_{i}*D*from the proof._{i} - If you delete vertex
*S*, does the new graph have degree sequence (*S*)?_{2} - Use the
*method in the proof*to modify the graph to be such that removing*S*gives a graph with degree sequence (*S*)._{2}
- Let us choose vertex
**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!)
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*G*? [^{c}*All vertices have degree k.*]
**(b)**If*G*is a connected graph, what can you say about*G*?^{c}**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!
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.
**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. |

## Homework Set XII (5/3, 9)

Read for Wed. 5/4 and Fri. 5/6: Sects. 8.4, 9.2.

Do for discussion Mon. 5/9:

Sect. 8.4, ## 1, 2, 4, 7.

Sect. 9.2, ## 2, 3.

## L2(a), L3(a), L6.

Do for discussion Tues. 5/10:

Sect. 8.4, ## 5, 8, 9.

Sect. 9.2, ## 6, 7.

## L5, L8.

Hand in Wed. 5/11:

Sect. 8.4, ## 3, 6, 11.

Sect. 9.2, # 4.

## L1, L1', L2(b), L3(b-d), L7, L9.

Hint for L1': Study the second proof of Theorem 9.1.4.

NOTE: There are really too many hand-in problems. The more important ones are 9.2.4, L1, L1', L2(b), L3(b), L7.

#### Definitions and Corrections

- Exercise 8.4.9 should read: Find the smallest graph that is planar and regular of degree 3 and has a plane drawing where every edge has the same geometric length.
- See the announcements page for more.

## Problem Set L

We define the girth of a forest (such as a tree) to be infinity. Then the girth of a graph is always ≥ 3.

L1.

(a) Prove **Theorem G**. If G is a planar graph and has girth ≥ g, and if p ≥ 3, then q ≤ [g/(g-2)](p-2).

(b) [ADDED 5/9] What does this say if g = 3?

(c) [ADDED 5/9] What does this say if G is bipartite?

L1'. [ADDED 5/9]

(a) Prove **Theorem CR**. If G is a graph (not necessarily planar) and has girth ≥ g, and if p ≥ 3, then cr(G) ≥ q - [g/(g-2)](p-2).

(b) What does this say if g = 3?

(c) What does this say if G is bipartite?

L1'' [ADDED 5/11] (This was proved in class, I think. I did prove the case g = 3 in class on 5/6. Feel free to use this theorem if it helps you.) **Theorem SPL**. If G is a graph (not necessarily planar) and has girth ≥ g, and if p ≥ 3, then σ(G) ≥ [(g-2]/g] q - (p-2).

L2. Use Theorem G to solve:

(a) Find cr(P), P = Petersen graph.

(b) Find cr(H), H = Heawood graph (Fig. 4.2.4).

L3. Use Theorem G to do (a, b, d).

(a) Prove: A cubic graph with girth g = 6 cannot be planar.

(b) Prove: A cubic graph with g ≥ 6 cannot be planar.

(c) Can a cubic graph with g = 5 be planar?

(d) Find a lower bound on cr(G) when G is cubic and has girth 6.

L4. Prove that cr(K_{6} - edge) = 2.

L5. Find θ(P), where P is the Petersen graph.

L6. Prove that θ(K_{n}) ≥ ceiling[(n+2)/6] for all n ≥ 1.

L7. Let c(G) = the number of cycles in the graph G.

(a) Prove *Theorem M*: If c(G) < min(c(K_{5}), c(K_{3,3})), then G is planar. (Hint: Use Kuratowski's theorem.)

(b) Evaluate the minimum in Theorem M.

(c) Use (b) to solve Exercise 8.1.3. (If you didn't solve (b), just prove the minimum in (b) is > 3; that should be enough for Exercise 8.1.3.)

L8. Let H = Heawood graph, Fig. 4.2.4.

(a) Prove σ(H) ≥ 2. (Hint: One way is to use Theorem G.)

(b) We know σ(H) ≤ 3. Decide whether σ(H) = 2 or 3.

L9. Prove σ(P) ≥ 2, where P = Petersen graph. (Thus σ(P) = 2, by Exercise 9.3.4.)

Go to homework index.

## Homework Set XIII (5/11)

For Wed.-Fri. 5/11-23: Read Sect. 9.3 (a continuation of splitting number, in the dual graph) and Sect. 10.3, pp. 225-227, pp. 228(bottom)-229, Theorem 10.3.3.

Do for discussion Wed. 5/11:

# M1.

Do for discussion Fri. 5/13:

Review problems:

Sect. 9.3, ## 2-5.

Sect. 10.3, # 1.

New material (graphs in surfaces):

Sect. 10.3, ## 7, 9.

# M2, M3 (at your discretion; I tend to prefer M3).

#### Terminology

- "Embedding" a graph is the technical term for drawing it without crossings or any other self-intersection.
- In Sect. 10.3 they often say "circuit of a rotation". What they mean is a region of an embedding of the graph in a surface. "Rotations" are a technical tool that I will avoid. I'll explain this in class.
- See the announcements page for the Euler formulas for graphs embedded in multiple tori.
- Here are pages with diagrams for T
_{1}(the torus) and T_{2}(the double torus), or both T_{1}and T_{2}, that you can use for drawing graphs.

## Problem Set M

Problem M1 is basic. The others are for those who enjoy embedding graphs on surfaces (as I do; it's recreational math).

M1. Try to embed non-planar complete graphs in the torus. Start with K_{5} (naturally), and if you succeed, try K_{6} and then K_{7} and then ....

M2. The same as # M1, for the double torus.

Use theorems in Section 10.3 to decide where to stop embedding in the double torus.

M3. Try to embed non-planar complete bipartite graphs in the torus. Start with K_{3,3} (naturally), and if you succeed, try K_{3,4} and then K_{3,5} and K_{4,4} – and then (we're getting into summer plans here) ....

Use theorems in Section 10.3 to decide where to stop embedding in the torus.

Go to homework index | announcements | course information | syllabus.