Prerequisites: Linear algebra (e.g. Math 2410, 2500-2501 or 2600) is required. It is also recommended that you have a little prior knowledge of graph theory (e.g., paths, cycles and trees) from an earlier mathematics course or from a computer science course. Otherwise you should consider taking Math 3700, Discrete Mathematics, instead.
Instructor: Mark Ellingham, SC 1514, phone 615 322 6670, email mark.ellingham@vanderbilt.edu.
Online resources: Most class resources will be available from http://www.math.vanderbilt.edu/ellingmn/6710/. Some resources may require using Brightspace.
Classes: Monday, Wednesday and Friday, 12:10-1:00 p.m., SC 1432.
Office hours: Monday and Wednesday, 1:10-2:00 p.m., and Thursday, 2:30-3:30 p.m.
Required textbook: Graph Theory, J. A. Bondy and U. S. R. Murty, Springer, 2008. There are two slightly different versions of this book available: the initial printing is different from later printings. Later printings have a "Preface to the second printing" on the page before the "Contents" page. Later printings are preferred but any printing is acceptable.
Assessment:
Assessment for this course will consist of three parts: homework
assignments, two tests, and a final examination. Your final grade will
be assigned based on a percentage calculated as follows.
| Homework assignments | 1/3 |
| Two tests | 1/3 (1/6 each) |
| Final examination | 1/3 |
Homework assignments: There will be five or six homework assignments, assigned at roughly two-week intervals throughout the semester. These will be due in class on a specified date, usually a Friday. You will have at least one week to do each assignment. If you have a good reason for submitting an assignment late, please see me (in advance if at all possible) to make arrangements. Otherwise, late assignments will receive a mark of zero.
Solutions to problems should be fully explained, using clear English sentences where necessary. Written problems must be submitted on paper, not in electronic form, unless explicit permission is given due to special circumstances. Solutions should be written or typed neatly on one side only of clean paper with straight (not ragged) edges. Multiple pages should be stapled (not clipped or folded) together. Marks may be deducted for violating these formatting requirements.
Practice problems: Problems for practice only (not for submission) may be given out from time to time, and will be discussed in class as time permits.
Tests: There will be two 50-minute in-class tests. Expected dates are Friday 27th September, and Friday 1st November. Test dates will be confirmed at least one week before the test.
Absence from a test will be excused only if authorized in advance by the instructor. In case of an emergency the instructor must be notified before the test begins if at all possible -- if you cannot reach me, leave a message with the Math office (615 322 6672). If sufficient notice of an absence is given, arrangements will be made for you to take the test early. If this is not possible your final mark at the end of the semester will be prorated to take into account the missed test. Absolutely no makeups will be given after the test. In the event of an unexcused absence, or if the instructor is informed unreasonably late of a forseeable absence, then the mark for the test will be recorded as zero.
Final examination:There will be a 120-minute final examination at 3 p.m. on Saturday 7th December. An alternate examination will not be offered.
Graduate credit: Students registered for Math 6710 will be given some homework problems that are more difficult than those for students registered for Math 4710.
Honor code: The Vanderbilt Honor Code applies as follows. All work is to be done individually unless working in groups is specified in writing by the instructor. You may not obtain assistance from any source, with the exception of hints given by the instructor.
Technology policy: Modern technology is useful but also distracting. Full attention and active participation are expected during class. Therefore, the following are prohibited during class: taking photographs or videos, use of earphones or earbuds, use of cellphones for any purpose. Laptop or tablet use for taking notes or other class-relevant activities that are not distracting to other students may be allowed at the instructor's discretion (let me know if you plan to use one regularly); your laptop or tablet must be silent. Other use of laptops or tablets is prohibited. Students requiring special accommodation should discuss their situation with the instructor.
Drop dates: The period to drop or add using YES ends on Wednesday 28th August. The period to drop using a paper form ends on Wednesday 4th September. The last day to withdraw from the class is Friday 18th October.
Outline: We will jump around in the book. I plan to cover:
| Basic definitions | 1.1-4 (as quickly as possible) |
| Subgraphs | 2.1-3, 12.1 |
| Moving around in graphs | 3.1, 3.3 |
| Trees | 3.2, 4.1-2 |
| Algorithm complexity | 8.1-3 |
| Tree search and construction | 6.1-2, 8.5 |
| Directed graphs | 1.5, 2.1, 2.5, 3.4, 6.3 |
| Network flows | 7.1-3 |
| Connectivity | 9.1-3, 5.1-2, 6.1 |
| Hamilton cycles | 18.1, 18.3 |
| Matchings | 16.1-5 |
| Colourings | 14.1, 14.7, 17.1-2 |
| Planar and embedded graphs | 10.1-3, 10.5-6, 11.1-2 |
The material covered may be adjusted if necessary. Besides the textbook, posted notes may be available, particularly when our treatment differs significantly from the one in the book.