# 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 on Wednesdays.

Week 10
 Monday, June 1: Read: Section 7.2 Hamiltonian graphs

Week 9
 Friday, May 29: Read: Section 7.1 and 7.2 Edge Coloring and Hamiltonian graphs
 Wednesday, May 27: Read: Section 6.2 and Section 6.3 Planarity and Coloring
Week 8
 Friday, May 22: Read: Section 6.2 and Section 6.3 Planar Graphs
 Wednesday, May 20: Read: Section 6.1 Planar Graphs Sect. 6.1 # 3, 5, 15, 17, 18 Sect. 6.2 # 2(a,b), 5 Sect. 6.3 # 4 (only for K_{4,4} and Petersen), 5, 18
 Monday, May 18: Read: Section 5.3 The Chromatic Polynomial
Week 7
 Friday, May 15: Read: Section 5.2 Graph Coloring
 Wednesday, May 13: Read: Section 5.1 Vertex Coloring Sect. 4.3 # 2 Sect. 5.1 # 12, 14, 20, 33 Sect. 5.2 # 1 Sect. 5.3 # 3, 4(a), 11, 18
 Monday, May 11: Read: Section 4.3 Networks

Week 6
 Friday, May 8: Read: Section 4.2 k-connectivity
 Wednesday, May 6: Read: Section 4.1 Connectivity Sect. 4.1 # 2, 3, 5, 8, 10, 11, 15 Sect. 4.2 # 4, 11, 12
 Monday, May 4: Read: Section 3.3 Factors

Week 5
 Friday, May 1: Read: Section 3.1 and 3.3 Matchings and Factors
 Wednesday, April 29: Read: Section 3.1 Matchings Sect. 3.1 # 5,8,9, 12, 24, 28 Sect. 3.3 # 2, 3, 6
 Monday, April 27: Read: Section 2.3 Shortest paths algorithms

Week 4
 Friday, April 24: Read: Section 2.3 Decompositions, Graceful labelings, Minimum spanning trees
 Thursday, April 23: Midterm 1: 4-6 PM in KH 004
 Wednesday, April 22: Read: Section 2.2 Spanning trees and counting Sect. 2.1 # 27, 32 Sect. 2.2 # 6, 7, 8, 17, 20 Sect. 2.3 # 3, 10, 16
 Monday, April 20: Read: Section 2.1 Distance

Week 3
 Friday, April 17: Read: Section 2.1 Trees
 Wednesday, April 15: Read: Sections 1.3 and 1.4 Digraphs Homework: (due Wednesday, April 22) Sect. 1.3 # 8 (b,c), 14, 17, 32 Sect. 1.4 # 9, 10, 15 Sect. 2.1 # 15, 23, 26
 Monday, April 13: Read: Section 1.3 Extremal Problems and Degree Sequences

Week 2
 Wednesday, April 8: Read: Sections 1.2 and 1.3 Eulerian graphs and Vertex degrees Homework: (due Wednesday, April 15) Sect. 1.2 # 9, 10, 17, 25, 38 Sect. 1.3 # 1, 12, 18
 Tuesday, April 7: Read: Section 1.2 Connectivity, Bipartite and Eulerian graphs
 Monday, April 6: Read: Section 1.2 Walks, Trails, Paths and Connectivity

Week 1
 Friday, April 3: Read: Section 1.1 Basic Definitions Homework: (due Wednesday, April 8) Sect. 1.1 # 10, 13, 16, 25, 29, 30
 Wednesday, April 1: Read: Section 1.1 Basic Definitions Homework: (due Wednesday, April 8) Sect. 1.1 # 10, 13, 16, 25, 29, 30
 Monday, March 30: First day of classes! Introduction to Graph Theory

Page created and maintained by R. Orellana