## Math 318, Graph Theory, Spring 2009

##### Professor Terry Loring, Department of Mathematics and Statistics,
• 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 so-called 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 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 Eight, March 9 - 13, 2009

• Monday: Hamiltonian graphs. § 3.3
• Homework 6, due March 23.
• Wednesday: Knight's Tours, six-by-six 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 multi-week emergences.

#### 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 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: In-degree and out-degree. § 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.