- 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. - The catalog states you need instructor's permission to take this class. This is not exactly as intended. If you have passed as semester of calculus you are fine. If you have not taken a semester of calculus, you may still be fine.
- 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.

- A list of topics
- Wednesday: Discuss policies, set midterm dates. The definition of a graph. §1.1
- Friday: Graphs as Models §1.2

- Monday: Definitions: isomorphism, bipartite, etc. §1.3
- Incidence information in the definition of a graph.
- Isomorphism as common relabelings.
- Homework 1, due January 29
- Bondy and Murty. A classic, now out of print.
- Since a few of you asked: Typesetting graphs in latex using xy-pic.
- Wednesday: §1.4
- Friday: Subgraphs §1.5

- Degree Sequences .
- Classifying small graphs (very small).
- Homework 2, due February 9
- Monday: Paths and walks, degree sequence. § 1.6
- Wednesday: bipartite graphs. Classifying "up to isomorphism" § 1.6
- Friday: adjacency matrix. § 1.7

- Homework 3, due February 16
- We are skipping § 1.8, for now.
- Trees, § 2.1
- Spanning Trees, § 2.2
- Classifying Trees.

- Bridges, § 2.3
- Minimum Weight Spanning Trees (Kruskal's Algorithm), § 2.4
- If you missed Wednesday's lecture, you can probably figure out Kruskal's algorithm just fine from this Minimum Weight Spanning Tree Example
- Don't worry about Prim's algorithm.

- Monday: A few review problems
- Wednesday: Midterm I
- Friday: Minimum Spanning Trees, § 2.4

- Monday: Shortest Path Problems, § 2.5
- Wednesday: Cut Vertices, indepenedent paths, § 2.6
- Examples of Dijkstra's algoritm to find lowest-cost paths
- Homework 4, due March 5
- Friday: Euler Circuits, § 3.1

- Homework 5, due March 21
- Monday: The Chinese Postman Problem, § 3.2
- Finding Euler Circuits, Solving Postman problems

- Homework 6, due March 19
- Knight's Tours, five by six
- We are skipping 3.4
- Friday: § 4.1 (Matchings)

- Monday: § 4.1 (Matchings)
- Wedneday: § 4.2 The Marriage Problem
- Friday: § 5.1, Plane and Planar Graphs.
- fun with the Peterson Graph
- Matching algorithms to be use in medical transplant matchings.
- We are skipping § 4.3-5.

- Homework 7, due April 13
- Monday: § 5.2, Euler's Formula.
- Wednesday: § 5.2
- Friday: § 5.3, Regular Polyhedra.

- Monday: § 5.4, Kuratowski's Theorem
- Wednesday:§ 5.5, Grinberg's Theorem
- Friday:§ 5.6, The dual of a plane graph
- Review problems Updated to have 5 problems

- Monday: Review. The midterm will cover: § 2.1-6, including cut vertices a bridges, not degrees of connectivity; § 3.1-2; § 4.1-2; § 5.1-2.
- Wednesday:
**Midterm II** - Friday:

- Homework 8, due May 2

- The final will cover all the material mentioned above for the first two midterms, plus § 6.1-2.
- Review problems, III

- the home page of the Office of the Registrar
- Wednesday, May 9,
**Final**10:00 a.m.-12:00 p.m.