Math 318, Graph Theory, Spring 2009
 The catalog states you need instructor's permission to take
this class. This is not exactly as intended. If you have passed
a semester of calculus you are fine.
If you have not taken a semester of calculus, but have top grades
in precalc courses adn want to take this class, you should contact me.

Catalog Course Descriptions
 There are many deadlines regarding grading and registration which are
listed by
the Office of the Registrar of the
University of New Mexico
 The text is A First Look at Graph Theory by
Clark and Holton, ISBN 9810204906.
 I'll send eMail via your UNM accounts.
Check this several times per week, or turn on forwarding to an account
you frequent:
How To #504  Forward Your UNM Electronic Mail.
Week One, January 19  23, 2009
Monday: Martin Luther King, Jr. Day, holiday, January 19.
 Wednesday: The definition of a graph. Loops vs. links. §1.1
 A more standard definition of a graph.
 Friday: Graphs as Models §1.2 An informal definition
of isomorphism. Definitions of degree, incidence, adjacence,
parallel edges.
 Isomorphism as common relabeling.
 Our book's definition of a graph excludes the socalled
null graph. This has zero vertices and zero edges.
Search on the phrase "is the null graph a pointless
concept" and enjoy.
Week Two, January 26  30, 2009
 Tentative grading percentages: MidI 25%; MidII 25%; HW 20%; Final 30%.
 Monday: Definitions: isomorphism, bipartite, odd
even, isolated, degree sequence. §1.3
 Homework 1 due by class time on February 2.
 Wednesday: The handshake lemma: vertex degrees sum
to twice the edge count. §1.4
 Friday: Subgraphs §1.5
 Despite what the text says on page 17, please distinguish
"is a subgraph" from "is isomorphic to a subgraph."
 It is known which sequences arise as degree sequences of some
simple graph. See problem 1.5.6 in the classic
"Graph Theory with Applications"
by Bondy and Murty.
Week Three, February 2  6, 2009
 Monday: Paths, walks, trails,
cycles, open walk, closed walk. Classifying
"up to isomorphism" § 1.6
 Homework 2 due by class time on February 9.
 Wednesday: definition of a regular graph.
Connected components. § 1.6
 Classifying up to isomorphism all simple graphs
with degree sequence (1,1,1,1,2,2,4).
 Friday: bipartite equals "no odd cycles."
Week Four, February 9  13, 2009
 Monday: adjacency matrix. § 1.7 Trees.
Pathes are unique in trees § 2.1
 Homework 3 due February 16.
 Wednesday: Classifying small trees.
 Friday: Spanning Trees, § 2.3 Classifying connected simple
graphs with five vertices and five edges.
Isomorphic simple graphs have isomorphic complements.
Week Five, February 16  20, 2009
Week Six, February 23  27, 2009
Week Seven, March 2  6, 2009
Week Eight, March 9  13, 2009
 Monday: Hamiltonian graphs. § 3.3
 Homework 6, due March 23.
 Wednesday: Knight's Tours, sixbysix
I was mistaken in class. The stategy we started with does work.
 Friday: Hamiltonian graphs, continued.
 We are skipping page 104 to 107 of § 3.3.
 We are skipping § 3.4
 Reminder: I do not accept late homework. If you can't attend class,
you can scan it and email it in, or slide it under by office door.
Also, I drop the two lowest scores, and will create makeup assignments
for multiweek emergences.
March 16  20: Spring Break , 2009
Week Nine, March 23  27, 2009
 Monday: Matchings § 4.1
 Homework 7, due March 30.
 Wednesday: The Marriage Problem,
Matchings in bipartite graphs § 4.2, 4.3
 Friday: Optimal assignments § 4.5
 We are skipping § 4.5.
Week Ten, March 30  April 3, 2009
Week Eleven, April 6  10 , 2009
 Monday: Review.
 The midterm will not cover § 4.5.
 Wednesday: April 8, Midterm II
 Friday: The dual of a plane graph, § 5.6.
Week Twelve, April 13  17 , 2009
 Monday: Directed graphs, basic definitions, § 7.1.
 Wednesday: Indegree and outdegree. § 7.2.
 Homework 9, due April 22.
 Friday: Tournaments. § 7.3.
Week Thirteen, April 20  24 , 2009
 Monday: Traffic flow. § 7.4.
 We are skipping the Hopcroft and Tarjan algorithm (pages 256 to
328).
 Wednesday: Networks. Flows and Cuts. § 8.1.
 Friday: Max Flow equals Min Cut.
 We are skipping § 8.2.
 Homework 10 (now 4 problems), due May 1.
Week Fourteen, April 27  May 1 , 2009
 Monday: Menger's theorem. Edge connectivity. § 8.3.
 Wednesday: Menger's theorem, edge and vertex versions.
 Friday: Graphs on a torus or on a Klein bottle.
Week Fifteen, May 4  8 , 2009
Finals Week May 1116, 2009
Math 327, Spring 2009