Course: MCS 423, Graph Theory
CRN: 38586 and 38587
Time: MWF 11:00-11:50am
Place: 208 Taft Hall

Professor: Dhruv Mubayi
Office: 620 SEO
Course Web Page:
Office Hours: Wednesday and Friday: 1-2

Grading Policies (tentative):
Attendance and class participation: 10%
Homework (Due Friday every two weeks): 15%
Two in-class midterms and Final exam, 25% each: 75%

All tests and exams will be IN PERSON, IN CLASS

Homework will be posted on BLACKBOARD. It must be turned in to BLACKBOARD as a (scanned or typed) pdf file before class starts on the day it is due. No late homework will be accepted.

Face Masks: Masks covering both the mouth and nose must be worn at all times by all students, faculty, and staff while on campus and inside any building regardless of vaccination status. If you do not wear a mask, you will be asked to leave the classroom and will not be allowed back in class unless or until you wear a mask. If you have forgotten your mask, you may pick one up from one of the student information desks on campus during the first two weeks of campus. Students who do not comply with the mask-wearing policy will be reported to the Dean of Students. Eating and drinking are not allowed in classrooms.

Disability Policy: Syllabus Statement UIC is committed to full inclusion and participation of people with disabilities in all aspects of university life. Students who face or anticipate disability-related barriers while at UIC should connect with the Disability Resource Center (DRC) at,, or at (312) 413-2183 to create a plan for reasonable accommodations. In order to receive accommodations, students must disclose disability to the DRC, complete an interactive registration process with the DRC, and provide their course instructor with a Letter of Accommodation (LOA). Course instructors in receipt of an LOA will work with the student and the DRC to implement approved accommodations.

Prerequisite: GRADE OF C OR BETTER IN MCS 261 OR EECS 360; AND MATH 310 OR 320 OR 330.

Description: The fundamentals of graph theory: trees, connectivity, Euler tours, Hamilton cycles, matchings, colorings and Ramsey theory. Although applications and some graph algorithms will be included, the course will focus on understanding the structure and properties of graphs as independent objects of study. We will attempt to cover most of Chapters 1--7 and Section 8.3 from the text.

Text (optional): West, Introduction to Graph Theory, Second Edition, Prentice Hall (class notes will suffice if you dont want to purchase the text)

Tentative Homework and Test Schedule:

Homework 1, Due Friday September 9
Homework 2, Due Friday September 23
Homework 3, Due Friday September 30

Test 1 -- Monday Oct 3

Homework 4, Due Friday October 14
Homework 5, Due Friday October 28
Homework 6, Due Friday November 11

TEST 2 -- FRIDAY November 18

Homework 7, Due Friday December 2