# Math 38: Graph Theory

Spring 2015

 Main Page Syllabus Homework

• The latest homework will always appear on top.

• In this class you will be writing lots of proofs, here is a pdf document with tips on writing proofs.

• If you are interested in learning to typeset mathematics here is a list of resources compiled by Prof. Weber on LaTex

Homework assignments

• Late Homework will not be accepted.
• Write the names of the people with whom you worked on the homework.
• Please make sure that what you turned in for homework is your own understanding of how to do the problems.

Homework due day: Homework will be assigned daily and will be collected once a week.

Week 9
 Friday, May 25: Read: Section 7.2 Hamiltonian Graphs
 Wednesday, May 23: Read: Section 7.1 Edge Coloring
 Monday, May 21: Read: Section 6.3 Planarity and Coloring

Week 8
 Friday, May 18: Read: Section 6.2 Characterization of Planar Graphs Homework: (due Friday, May 25) Sect. 6.1 # 17 Sect. 6.2 # 4 (use Kuratowski's Theorem to show they are nonplanar or draw them as planar graphs), 5
 Wednesday, May 16: Read: Section 6.1 Planar Graphs Homework: (due Friday, May 25) Sect. 6.1 # 9, 10, 15
 Monday, May 14: Read: Section 5.3 Chromatic Polynomial Homework: (due Friday, May 25) Sect. 5.3 # 4(a), 11, 18

Week 7
 Friday, May 11: Read: Section 5.2 Graph Coloring Homework: (due Friday, May 18) Sect. 5.1 # 12, 14 Sect. 5.2 # 1
 Wednesday, May 9: Read: Section 5.1 Graph Coloring Homework: (due Friday, May 18) Sect. 5.1 # 19, 20, 33
 Monday, May 7: Read: Section 4.3 Networks Homework: (due Friday, May 18) Sect. 4.2 # 11, 12 Sect. 4.3 # 2

Week 6
 Friday, May 4: Read: Section 4.2 k-connectivity Homework: (due Friday, May 11) Sect. 4.1 # 5, 15 Sect. 4.2 # 4
 Wednesday, May 2: Read: Section 4.1 # 5, 15 Connectivity Homework: (due Friday, May 11) Sect. 4.1 # 8, 10, 11
 Monday, April 30: Read: Section 3.3 Matchings and Factors Homework: (due Friday, May 11) Sect. 3.3 # 2, 3, 6

Week 5
 Friday, April 27: Read: Section 3.1 Min-Max Theorems Homework: (due Friday, May 4) Sect. 3.1 # 4, 5, 9
 Wednesday, April 25: Read: Section 3.1 Matchings: Hall's Theorem Homework: (due Friday, May 4) Sect. 3.1 # 8, 12, 28
 Monday, April 23: Read: Section 2.3 Dijkstra's and Breath First Search algorithms Homework: (due Friday, May 4) Sect. 2.3 # 1, 10, 16
Week 4
 Friday, April 20: Read: Section 2.3 Optimization and Trees Homework: (due Friday, April 27) Sect. 2.2 # 17, 20 Sect. 2.3 # 3
 Wednesday, April 18: Read: Section 2.2 Trees and Counting Homework: (due Friday, April 27) Sect. 2.2 # 6, 7, 8
 Monday, April 16: Read: Section 2.1 Distance Homework: (due Friday, April 27) Sect. 2.1 # 15, 32, 44

Week 3
 Friday, April 13: Read: Section 2.1 Trees Homework: (due Friday, April 20) Sect. 2.1 # 18, 23, 27
 Wednesday, April 11: Read: Section 1.4 Digraphs Homework: (due Friday, April 20) Sect. 1.4 # 9, 10, 15
 Monday, April 9: Read: Section 1.3 Extremal Problems and Degree Sequences Homework: (due Friday, April 20) Sect. 1.3 # 8, 32, 41

Week 2
 Wednesday, April 4: Read: Section 1.3 Eulerian Graphs and Vertex degrees Homework: (due Friday, April 13) Sect. 1.3 # 1, 12, 18
 Monday, April 2: Read: Section 1.2 and Section 1.3 Connectivity, bipartite and Eulerian Graphs Homework: (due Friday, April 13) Sect. 1.2 # 16, 25, 38

Week 1
 Friday, March 30: Read: Section 1.2 Walks, Trails, Paths and Connectivity Homework: (due Friday, April 6) Sect. 1.2 # 10, 17, 18
 Thursday, March 29: Read: Section 1.1 Basic Definitions - part 2 Homework: (due Friday, April 6) Sect. 1.1 # 18, 25, 30
 Wednesday, March 28: Read: Section 1.1 Basic Definitions - part 1 Homework: (due Friday, April 6) Sect. 1.1 # 10, 13, 16
 Monday, March 26: First day of classes! Introduction to Graph Theory

Page created and maintained by R. Orellana