COURSE NUMBER: MATH 5450
TIME: 1:20-2:40 TR; PLACE: Gilbreath Hall 304 CALL# 14033
INSTRUCTOR: Robert "Dr. Bob" Gardner; OFFICE: Room 308F of Gilbreath Hall
OFFICE HOURS: By appointment; PHONE: 439-6979 (Math Office 439-4349)

E-MAIL: gardnerr@etsu.edu
WEBPAGE: www.etsu.edu/math/gardner/gardner.htm.

TEXT: Graph Theory by J. A. Bondy and U. S. R. Murty, Graduate Texts in Mathematics 244 (Springer, 2008).

PREREQUISITE: The catalog states that "admission to the math graduate program or permission" are the formal prerequisite. Students must have some background in proving theorems and a working knowledge of linear algebra, but all graph theory definitions will be covered and we will start from first principals of graph theory.

DESIRE2LEARN: I will not rely much on the Desire2Learn ("D2L") website. Instead, I will simply post all material directly on the internet. However, I will post your grades and homework solutions on D2L.

CLASS NOTES: We will use digital notes for the presentation of definitions, examples, and proofs of some theorems. Limited marginal notes, additional examples, and further explanations will be given on the whiteboard. Copies of the notes are online for Chapters 1 to 5 and Chapters 9 to 19. You should read the online notes to be covered in class before each class (we may not have class time to cover every little detail in the online notes). Try to understand the definitions, the examples, and the meanings of the theorems. After each class, you should read the section of the book covered in that class, paying particular attention to examples and proofs.

ABOUT THE COURSE: Graph theory is a relatively new area of math. It lies in the general area of "discrete math" (as opposed to continuous math, such as analysis and topology), along with design theory and coding theory. Historically, it is motivated by applied problems and still finds numerous applications, particularly in computer science (such as network design and the efficiency of algorithms). However, today it is a very vibrant area of pure mathematical research. ETSU has had a number of research graph theorists over the past several years, including Drs. Lawson, D. Knisley, and Haynes (each has retired), Dr. Boland (deceased, 2006), and Dr. Beeler (and, part-time, Drs. Godbole, Gardner, and Keaton). This class is a continuation of the fall 2022 Graph Theory 1 (MATH 5340), so we will finish Chapter 4 on trees and partially cover chaptes 5 and 9. The rest of the class will be spent on planar graphs, vertex colorings, and the Four Color Theorem.

OUTLINE: We will cover topics from the following list. There is not enough time to cover all of this (of course), so emphasis will be put on topics of student interest.
Chapter 4. Trees (partial): Fundamental cycle, even subgraphs, fundamental bonds, cyclomatic number.
Chapter 5. Nonseparable Graphs (partial): Cut vertex, separation of a connected graph, nonseparable graph, block of a graph.
Chapter 9. Connectivity (partial): Vertex connectivity, local connectivty, vertex cuts, edge connectivity, essential edge connectivity, three-connected graphs, contractions and expansions of three-connected graphs.
Chapter 10. Planar Graphs: Planar/nonplanar graph, points and lines of a planar embedding, curve, closed curve, simple curve, Jordan Curve Theorem, subdivision of a graph, face of a graph, boundary of a face, dual of a graph, plane dual, plane triangulation, Euler's Formula, Kuratowski's Theorem, minor of a graph, orientable/nonorientable surface, projective plane, classification theorem for surfaces, Euler characteristic of a surface.
Chapter 11. The Four-Colour Problem: Four-Colour Problem/Conjecture (face, vertex, edge versions), k-face colouring, Appel and Haken's proof of the Four-Colour Theorem, k-vertex-colouring, k-edge-colouring, Five-Colour Theorem.
Chapter 14. Vertex Colourings: Chromatic number, Greedy Colouring Heuristic, Brook's Theorem, Path Partition Conjecture, colour critical graphs, girth and chromatic number, perfect/imperfect graphs, list colourings, list chromatic number, adjacency polynomial, chromatic polynomial.
Chapter 15. Colourings of Maps: Chromatic numbers of surfaces, Heawood's Inequality, the Four-Colour Theorem (smallest counterexample, Kempe chains, Kempe interchange, unavoidable configurations, discharging, history, controversy), list colourings, Hadwiger's Conjecture.
Chapter 16. Matchings (maybe): matching, perfect matching, maximal matching, matchings in bipartite graphs, covering, covering number, matchings in arbitrary graphs, factors.

GRADES: Since this is an online class, your grade will be determined by the average on the assigned homework exercises. Grades will be assigned based on a 10 point scale with "plus" and "minus" grades being assigned on a 3 point subscale (for example, a 90, 91, 92 is an A-).

HOMEWORK: Homework will be assigned and collected at one week intervals. It will normally be due on Saturdays at midnight and you will be expected to submit scans in PDF of your work to D2L. YOU MUST SHOW ALL DETAILS ON THE HOMEWORK PROBLEMS!!! Justify every step and claim you make - this is how you convince me that you know what you are doing. You may find some answers online, but these rarely sufficiently justify all steps and are unacceptable as homework solutions.

ACADEMIC MISCONDUCT: While I suspect that you may work with each other on the homework problems, I expect that the work you turn in is your own and that you understand it. Some of the homework problems are fairly standard for this class, and you may find proofs online or in an online version of the solutions manual. The online proofs may not be done with the notation, definitions, and specific methods which we are developing and, therefore, are not acceptable for this class. If I get homework from two (or more) of you that is virtually identical, then neither of you will get any credit. If you copy homework solutions from an online source, then you will get no credit. These are examples of plagiarism and I will have to act on this as spelled out on ETSU's "Academic Integrity @ ETSU" webpage (last accessed 1/7/2023). To avoid this, do not copy homework and turn it in as your own!!! Even if you collaborate with someone, if you write the homework problems out in such a way that you understand all of the little steps and details, then it will be unique and your own work. If your homework is identical to one of your classmates, with the exception of using different symbols/variables and changing "hence" to "therefore," then we have a problem! If you copy a solution from a solution manual or from a website, then we have a problem! I will not hesitate to charge you with academic misconduct under these conditions.

SYLLABUS ATTACHMENT: You can find an on-line version of the university's syllabus attachment (which contains general information concerning advisement, honor codes, dropping, etc.; last accessed 1/7/2023).

COVID-19 AND THIS CLASS: I will likely wear a mask during class. This may result in somewhat muffled lectures, but all classnotes are online and the lectures will closely adhere to the notes. Since this is a small class, then students are encouraged to socially distance by sitting at least 6 feet apart. Remember, students are "strongly encouraged to get a vaccine." Vaccinations are the best way to avoid spreading COVID-19.
PLANS TO DEAL WITH POTENTIAL EXPOSURE/ILLNESS: I will set up a meeting through Zoom for each class and (if all of the technology works) I will record each class. If you are not feeling well, then do not come to class! If you fear that you have been exposed and are concerned that you might be infected, then do not come to class! If you have tested positive for COVID then definitely do not come on campus for the suggested period of time! You can attend the Zoom meeting and ask questions during class (the classroom is wired for sound, so I will be able to hear you). I will follow this plan myself. If I am not feeling well or suspect that I have been exposure to COVID, then I will replace the on-ground class with the Zoom meeting which I will run from home (assuming that I am feeling well enough to lecture online).

SUPPLEMENTAL REFERENCES:

• Information on the Nova episode The Mathematical Mystery Tour from 1985, a one hour show covering lots of math history, can be found on my webpage A Mathematical Mystery Tour 25th Anniversary Webpage . The webpage includes a link to the YouTube site which contains the show.
• A lighter documentary on the history of math is The Story of One, narrated by Monty Python-er Terry Jones. It is also a BBC production and dates from 2005. If you are involved in teaching, this is a nice documentary which should be accessible by high schoolers and middle schoolers. It is on TopDocumentaryFilms (last accessed 1/7/2023).
• An online copy of Bondy and Murty's 1976 Graph Theory with Applications is available from Web.Archive. This book is aimed at upper level undergraduates and beginning graduate students (that is, it is appropriate for the cross listed "Introduction to Graph Theory" class [MATH 4347/5347]).
• A set of notes I have prepared to Introduction to Graph Theory (MATH 4347/5347) is available. These notes are based on Nora Hartsfield and Gerhard Ringel's Pearls in Graph Theory: A Comprehensive Introduction (San Diego: Academic Press, 1994).
• The Institue of Combinatorics and Its Applications has access free access to recently published papers from it's Bulletin of the ICA:

IMPORTANT DATES: (see the official ETSU calendar for more details; accessed 1/7/2023):

• Tuesday, January 17 = First day of classes.
• Monday, January 30 = Last day to drop without a grade of "W."
• Tuesday, January 31 = Begin late add with dean's permission.
• Wednesday, March 1 = Last day for Graduate Students to apply for graduation and submit committee forms for Summer 2023 or Fall 2023 graduation.
• Tuesday, March 7 = Last day to drop without dean's permission.
• Monday-Friday, March 13-19 = Spring Break, no classes.
• Monday, March 13 = Last day to schedule oral defense of thesis for May 2023 graduation.
• Monday, March 27 = Last day to complete oral defense of thesis for May 2023 graduation.
• Friday, April 7 = University Closed, no classes.
• Wednesday, April 26 = Last day to withdraw from the university.
• Friday, April 28 = Last day of classes.

Return to Dr. Bob's webpage

Last updated: April 15, 2023.