Graph Theory Homework Problems
Math 38.Graph Theory
Spring 2010
· Instructor: Sergi Elizalde
· Lectures: MWF 12:301:35 in Kemeny 108
· Xperiod: Tu 1:001:50
· Office Hours: M 1112:30, Th 2:303:30.
· Office: Kemeny 332
· Email:
· Phone: 6468191
Announcements
Here is this week's homework assignment.
The class on Friday, May 28 will be moved to the Xhour on Tuesday, May 25.
The takehome final exam will be handed out on Wednesday, May 26, and due on June 2, the last day of class. It will cover everything we have done up to Chapter 5 (included).
The grader for the course is Will Chen.
Course description
This course will cover the fundamental concepts of Graph Theory: simple graphs, digraphs, Eulerian and Hamiltonian graphs, trees, matchings, networks, paths and cycles, graph colorings, and planar graphs. Famous problems in Graph Theory include: the Minimum Connector Problem (building roads at minimum cost), the Marriage Problem (matching men and women into compatible pairs), the Assignment Problem (filling n jobs in the best way), the Network Flow Problem (maximizing flow in a network), the Committee Scheduling Problem (using the fewest time slots), the Four Color Problem (coloring maps with four colors so that adjacent regions have different colors), and the Traveling Salesman Problem (visiting n cities with minimum cost).
Textbook
Introduction to Graph Theory by Douglas B. West, Second edition (available at Wheelock Books).
Tentative syllabus
This syllabus is subject to change, but it should give you an idea of the topics I am planning to cover.
 Chapters  Brief Description 
Week 1  1.1, 1.2  Definitions, examples of problems in graph theory, isomorphisms. Paths, walks, cycles, components, bipartite graphs, Eulerian graphs.

Week 2  1.3, 1.4  Vertex degrees, extremal problems, degree sequences. Directed graphs, de Bruijn cycles, orientations.

Week 3  2.1  Trees and distance, spanning trees, radius and diameter.

Week 4  2.2  Enumeration of trees, Cayley’s formula, Prüfer code. Counting spanning trees, deletioncontraction, the matrix tree theorem, graceful labelings.

Week 5  2.3  Minimum spanning trees (Kruskal’s algorithm), shortest paths (Dijkstra’s algorithm).

Week 6  3.1  Matchings, Hall's theorem, minmax theorems, maximum matchings, independent sets, vertex and edge coverings.

Week 7  4.1, 4.2  Cuts, connectivity, edgeconnectivity, blocks, kconnected graphs, Menger’s theorem, line graphs . 
Week 8  4.3  Network flow problems, maxflow mincut theorem, FordFulkerson algorithm. 
Week 9  5.1, 5.3  Vertex colorings, bounds on chromatic numbers. Chromatic polynomials. 
Week 10  6  Planar graphs, Euler's formula, Kuratowski's theorem, five and four color theorems. 
Grading
The course grade will be based on the homework (20%), two midterms (25% each), and a final exam (30%).
Homework
There will be homework due roughly every week. It will consist typically of a reading assignment (of the part of the book covered in class) and some problems. All the homework assignments are posted here. You are encouraged to collaborate on the homework, but what you write has to be your own understanding of how to do the problem. You must state what sources you have consulted, with whom you have collaborated, and from whom you have received help. No late homework will be accepted.
Students with disabilities: Students with learning, physical, or psychiatric disabilities enrolled in this course that may need disabilityrelated classroom accommodations are encouraged to make an office appointment to see me before the end of the second week of the term. All discussions will remain confidential, although the Student Disability Services office may be consulted to discuss appropriate implementation of any accommodation requested.

Announcements: 
The midterm exams will be on Monday,February 3 and Monday, March 24 
I will give you an extension on the homework assignment #2 until Friday, February 14, 2003 and it should be turned in to Li Gang's mailbox in Ross N524 no later than 2:30pm. 
The problem asking for the number of spanning trees of a wheel is hard (although not impossible) and so I am making it a bonus question for the homework assignment. Here is a hint: HINT 
The 4th homework assignment is a bit long and we won't get to the topic of the last two problems on the homework until the last day of class so I will make due any 6 of the 8 problems. Hand in your homework either on the last day of class or to the TA's mailbox (Li Gang) in Ross N524 (it is due April 4 at 2:30pm). 
I haven't exactly covered every section of the book this term. In class I have covered (at least roughly): Ch 1.1, 2.2, 2.3, 2.4, 3.5, 3.6, 3.7, 3.8, 4.9, 4.10, 5.12, 5.13, 5.14, 5.15, 6.17, 6.21, 8.25, 8.26 and I hope to do 8.29 before the end of class. 
The final exam will be Tuesday, April 8 from 12pm3pm in CLH G. 
I will have office hours Monday, April 7 from 2pm4pm. 
(4/9/03) Grades for the course will be posted here in a few weeks. 
(4/28/03) I have finished making up the grades. I am posting them here. 
York University Professor Mike Zabrocki MW 2:304pm CLH 110 Office: Ross S615 Office hours: W45pm F11:301pm or by appointment 
Best way to contact me: 
Topics: Graphs, digraphs. Eulerian and Hamiltonian graphs. The travelling salesman. Path algorithms; connectivity; trees; planarity; colourings; scheduling; minimal cost networks. Tree searches and sortings, minimal connectors and applications from physical and biological sciences. 
Course description: A first course in graph theory. After considering introductory material on graphs and properties of graphs, we shall look at trees, circuits and cycles. Graph embeddings, labelings andcolourings, with some applications, will also be covered. 
Prerequisite: At leastsix credits from 2000level (or higher) MATH courses (without second digit5, or second digit 7 in the case of Atkinson), or permission of the instructor. 
Text: Introduction to Graph Theory by Robin Wilson (4th ed) 
The grade in this course willbe based on the following criterion: 
Problem Session: Wednesday 4:30pm N501 Teaching Assistant: Li Gang 
The homework is for your benefit so it is in your interest to spend some time doing the problems each week. Struggle with them for a while before getting help from either myself, the TA, or your fellow students. Do not copy homework assignments. 
Week  Topic/sections in text  Homework  Solutions 
1  What is a graph? graph isomorphisms  
2  graph isomorphisms, bipartite and regular graphs  HW #1  
3  Eulerian and Hamiltonian graphs  HW #1  
4  Hamiltonian graphs, algorithms and trees  HW #2  
5  Midterm Monday Feb 3, trees  
6  Reading week  
7  planar graphs, Euler's theorem  HW #3  HW #2 
8  dual graphs, graph coloring  
9  graph coloring and the 4/5 color theorem  
10  coloring polynomial, matching theorem  HW#4  HW #3 
11  midterm, transversal theory  
12  transversals, flows  HW #4 
In class handouts (if you missed a day or lost your copy, they should allbe here):
 syllabus (1/8/03)
 A bunch of pairs of graphs Tell me if they are isomorphic or not (1/13/03)
 homework #1  due: 1/29/03 (1/20/03)
 homework #1 solutions
 homework #2
 homework #2 solutions (2/23/03)
 homework #3 (2/24/03)
 homework #3 solutions (3/17/03)
 homework #4 (3/19/03)
 homework #4 solutions (4/2/03)
Links :
 Three unsolved math problems worth $1M (NOT!)  one of them is Ramsey theory
 a list of the number of graphs with n vertices
 The four color theorem
One thought on “Graph Theory Homework Problems”