Skip Navigation

MATH412 - Graph Theory

Course Details

Course Code: MATH412 Course ID: 4545 Credit Hours: 3 Level: Undergraduate

This course studies set theory, counting techniques such as permutations, combinations, generating functions, partitions and recurrence relations, Polya’s theorem, Hamiltonian and Euclidian properties of graphs, matchings, trees, coloring problems and planarity. (Prerequisite: MATH305)


Course Schedule

Registration Dates Course Dates Session Weeks
06/28/21 - 12/03/21 12/06/21 - 01/30/22 Fall 2021 Session D 8 Week session
09/28/21 - 03/04/22 03/07/22 - 05/01/22 Winter 2022 Session D 8 Week session

Current Syllabi

After successfully completing this course, you will be able to

CO-1 Explain basic definitions and properties associated with simple planar graphs, including isomorphism, connectivity, and Euler's formula.
CO-2 Describe when a graph is a useful mathematical tool to solve problems in mathematics, the sciences and the environment.
CO-3 Describe the difference between Eulerian and Hamiltonian graphs.
CO-4 Use graph theories to solve mathematical problems.
CO-5 Formulate logical and coherent proofs including proofs by contradiction and induction.
CO-6 Analyze studies of topics related to graph theory including combinatorics and computer science.

Reading Assignments: Reading assignments are provided each week. These assignments flow into the Forum discussions and homework problems. Reading assignments are not graded directly. Your conceptual understanding, ability to solve problems, and ability to synthesize material will be evaluated using quizzes, projects, and a final exam.

Forum and Homework Assignments: Mathematics is not a spectator sport. In order to learn the language of Mathematics, you must be engaged with the material. It is critical that you spend time thinking, considering examples, working problems, and discussing ideas with others. The Forums are evaluated in three areas: quantity of posts, quality of posts, and value of interactions. Initial forum posts are due each week. Your initial post must be made on or before Wednesday, each week. Homework assignments much be attached to your initial post. You may attach your Homework assignment at any time through Sunday of the week it is due. Optional homework problems are for your benefit and are not required for submission.
+ The Homework are graded for completeness, correctness, and clarity.

+ The Forums are evaluated in three areas: quantity of posts, quality of posts, and value.

Quantity – The initial post for each Forum includes at least 250 words, and a minimum of two interaction posts are required per Forum using at least 100 words each.

Quality – High quality posts are critical to the development of everyone in the course. The overall quality of your posts is evaluated.

Value – Banal posts such as “Good work” and “Nice conclusion” provide no value to the Forum conversations. The key to the Forums is quality interaction. Superior posts promote a valuable conversation and meaningful interaction.

Forum Note: you cannot score points for the quality and value of a post if you fail to meet the minimum quantity.

Writing Assignment: Written communication is a key piece of modern mathematics. The Forums as well as many of the homework problems ask you to develop an argument and write it clearly. In addition to the Forums and homework, you are required to write two formal proofs as writing assignments. These assignments are evaluated according to their validity, readability, and fluency. The definitions for those concepts are given here.

Validity – Validity corresponds to the validity of your arguments. It addresses the extent to which your method is appropriate, your calculations are correct, and your deductions follow the rules of logic.

Readability – If your written work is not readable it cannot be assessed. Since the ability to communicate Mathematics is a focal point for this class, special attention will be paid to the readability of your work.

Fluency – Mathematics is a concise and precise language, and I wish to enhance your fluency. Therefore, part of every assessment will focus on your ability to incorporate correct, established notation and terminology into your written work.

Quizzes: These are the core assessment tools for the assigned readings and homework. Your work will be graded for correctness, completeness, and clarity.

Projects: As with the writing assignment, the projects provide you with an opportunity to improve your Mathematical communication. For the projects you will need to effectively communicate your ideas in a slideshow presentation that includes an audio track. Using audio files you will explain your work with clarity and precision. This assignment will be evaluated in a manner similar to the writing assignments. However, an additional criterion will be evaluated.

Multimedia – A completely integrated presentation incorporating written work with emphases and accompanying audio. The total effect of the presentation is evaluated.

Final Exam: As with the quizzes, the final exam is a core assessment tools for the assigned readings and homework. The final exam is comprehensive, and your work will be graded for correctness, completeness, and clarity.

NameGrade %
Forums 23.00 %
Honor Pledge 0.96 %
Introduction Forum 0.96 %
Week 1 Forum & Homework 2.88 %
Week 2 Forum & Homework 2.88 %
Week 3 Forum & Homework 2.88 %
Week 4 Forum & Homework 2.88 %
Week 5 Forum & Homework 2.88 %
Week 6 Forum & Homework 2.88 %
Week 7 Forum & Homework 2.88 %
Week 8 Feedback 0.96 %
Writing 30.00 %
Project 1 10.00 %
Project 2 10.00 %
Writing Assignment 10.00 %
Quizzes 25.00 %
Quiz 1 5.00 %
Quiz 2 10.00 %
Quiz 3 10.00 %
Final Exam 22.00 %
Final 22.00 %

Additional Resource

Graph Theory with Applications
By J.A. Bondy and U.S.R. Murty
5th printing, 1982
Sole Distributer: Elsevier Science Publishing Co, Inc.

Web Sites

In addition to the required course texts, many public domain web sites are useful. Here are a few sites to consider if you want to view topology and modern mathematics from a different perspective. Please abide by the university’s academic honesty policy when using Internet sources. Note web site addresses are subject to change.

Site Name

Web Site URL/Address




Another Introduction

Undirected Graphs

Isometric Graphs

Euler's Theorem

Spanning Trees

Minimum Spanning Tree

Shortest Path

Nearest Neighbor

Dr. Herke Introduction

Dr. Herke Examples

Dr. Herke Families

Dr. Herke Matrices

Dr. Herke has an extensive video lecture series on Graph Theory. Only four of her presentations are listed above. If you want more information, please follow any of her video links and look for more lessons.

Book Title:Introduction to Graph Theory, 5th Ed - the VitalSource e-book is provided inside the classroom
Publication Info:VS-Pearson
Unit Cost:$176.64
Electronic ISBN:9781269980487
Electronic Unit Cost:$35.00

Previous Syllabi

Not current for future courses.