There will be notes posted on this page, in particular homework assignments. I will expect you to check this page at least twice each week, so you might as well bookmark it.

General Information

• Course Description
• My office hours will be MWF 2:00-3:00 in the atrium of Dane Smith Hall.
• If you cannot make my official office hours, you are encouraged to make appointments to see me. Use eMail (loring@math.unm.edu) or talk to me at the end of class.
• You are required to have a CIRT eMail address and to check that mail at least twice each week.
• If you want your CIRT eMail to be automatically forwarded to another eMail address, you can get help from CIRT.
• You are required to check this blog twice each week.
• There will be a midterm in Week Five, worth 20%.
• There will be a midterm in Week Eleven or Twelve, worth 25%.
• There will be about ten homework assignments, worth 25%.
• The final during finals week, worth 30%.
• No late homework will be allowed. Major unforeseen events will be handled on an individual basis, perhaps using alternate assignments.
• Your two lowest homework scores will be dropped.
• You will need to be able to view pdf and flash files.
• We will cover all the material in the book, and more.

Week One, January 17-21, 2005

• Monday was a holiday.
• This week is the time to discuss special needs, especially any that will relate to the dates I pick for the midterms. Those dates will soon be set in stone.
• Wednesday was mostly to negotiate the above details.
• We spent a few minutes discussing sets, ordered pairs, and sets of ordered pairs.
• We discussed the word blog.
• Friday: §1.1-1.5 (skipping §1.6, for now).

Week Two, January 24-28, 2005

• This week we will finish a few items from Chapter one and then cover the first two or three sections in Chapter two. Isomorphism will be the hardest topic for most of you.
• First Homework and Supplemental Reading for Chapter One. Due Monday, January 31, in class. Don't be late.
• Monday: §2.1.
• Wednesday: isomorphism, §2.2.
• Friday: walks, and connectedness, §2.3.
• I picked the midterm dates. See below.

Week Three, January 31 - February 4, 2005

• Monday--More on isomorphism, more on connectedness.
• Second Homework and Examples of Isomorphism, Due Monday, February 7.
• Wednesday: §2.4.
• Friday: §3.1.
• An example of finding an Euler Walk,

Week Four, February 7-11, 2005

• Third Homework Due Monday, February 14.
• Monday: Hameltonian cycles, §3.2.
• What the heck is a multigraph/pseudograph?
• Wednesday: Pseudographs, more on isomorphism. Duals, Symmetry and Small Graphs
• Friday: Pseudographs, more on isomorphism.
• Review problems to try before Monday

Week Five, February 14-18, 2005

• Review
• Midterm, Wednesday February 16.
• Friday: Introduction to Trees, §1.6 and §4.1.

Week Six, February 21-26, 2005

• Monday: §4.1 continuted, and classifying small trees.
• Wednesday —> §4.3
• Homework number 4 corrected 2/25, due March 2.
• Here's a little information on how you can tell if two trees are not isomorphic.
• Friday: §5.1 (Ramsey Numbers).
• A few small comments on trees and spanning trees.
• An animation of the selection of a minimum weight spanning tree. (Might help, can't hurt.)

Week Seven, February 28 - March 4, 2005

• Monday: §5.2. (The Marriage Theorem)
• Bipartite Graphs and The marriage problem.
• A proof of the Marriage Theorem, (optional reading).
• Wednesday: §6.1, §6.2 and §6.4.
• Homework #5 due March 9.
• (Closed) Knight's Tours on small chess boards.
• Friday: Euler digraphs and de Bruijn digraphs.

Week Eight, March 7-11, 2005

• Monday: Tournaments: § 7.2
• Wednesday: Tournaments: § 7.2 and 7.3
• Friday: Balanced Social Networks: § 8.1

Week Nine, March 21-25, 2005

• Should you ever have a need for this, here's how to typeset graphs in Latex
• Homework #6 due March 28.
• Monday: §7.1 & 8.2
• We're skipping §8.3
• Wednesday: §9.1
• Friday: §9.1
• (Closed) Knight's Tours on a 5 by 6 chess board (we'll talk about this in a week or so).

Week Ten, March 28 - April 1, 2005

• Homework #7 due April 6.
• Monday: §9.2
• Wednesday: §9.3
• Friday: §10.2

Week Eleven, April 4-8, 2005

• Midterm, Wednesday April 6.
• Friday: §10.1

Week Twelve, April 11-15, 2005

• Monday: Discussion.
• I could not find anything really readable regarding entropy of graphs.
• The other topics of interest are random graphs and connectedness of graphs.
• One electronic book: Bondy and Murty, Graph Theory with Applications available for download at Professor Bondy's website.
• A more advanced electronic book: Diestel, Graph Theory available at Professor Diestel's website.
• An applet to help you learn Dijkstra's algorithm on a network.
• Wednesday: Networks, Dijkstra's algorithm.
• Friday: definition of k-connectivity, graphs of high average degree, contractions. Read: Diestel § 1.4.

Week Thirteen, April 18-22, 2005

• Monday: Diestel § 1.7, 3.1.
• An example of blocks and a block graph.
• Homework #8 due April 27.
• Wednesday: Diestel § 3.2 -- just the last paragraph on page 46..
• Friday: Diestel § 3.3. -- just page 50 and page 55.
• An expanded proof of Menger's theorem.
• An example demonstrating the proof of Menger's theorem.

Week Fourteen, April 25-29, 2005

• Monday: More about Menger's theorem and Blocks.
• Wednesday: Starting Random Graphs, Diestel § 11.1.
• Friday: Random Graphs

Week Fifteen, May 2-6, 2005

• Monday: Random Graphs
• Review/extra credit problems, REVISED
• Wednesday: Review
• Friday: Review

Finals Week

• Wednesday, May 11: Final Exame 12:30-2:30 p.m.
• Final exam schedule
• You should study from the midterms and midterm review sheets.
• 80% of the test will be on material we covered before the second midterm.
• Topics to be covered that were not in Chartrand:
  • k-connected and k-edge connected.
  • Construcion of 2-connected graphs.
  • Blocks and block graphs
  • Menger's theorem (statement and max-flow/min-cut problems, not the algorithm I described).