Course: MCS 423, Graph Theory

CRN: 38586 and 38587

Time: MWF 11:00-11:50am

Place: 216 Taft Hall

Professor: Dhruv Mubayi

Office: 620 SEO

E-mail: mubayi@uic.edu

Course Web Page: http://www.math.uic.edu/~mubayi/423/Fall24/423Fall24.html

Office Hours: TBD

Grading Policies:

Attendance and class participation: 15%

Homework (Due Friday every two weeks): 15%

Three in-class midterms, 35% each (I will drop the lowest): 70%

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. You can discuss homework with each other but must write it up
independently with no help from anyone else. Do not search the web for solutions, but you are permitted to search the
web for definitions (or just email me).

Accommodations: Disability Policy - Students with disabilities who require accommodations for access and participation in this course must be registered with the Office of Disability Services (ODS). Please contact ODS a 312/413/-2183 (voice) or 312/413-0123 (TTY).

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

Course 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.

Course Goals and Learning Objectives: To gain proficiency in the main themes of modern graph theory.

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

Policy for missed or late work, including acceptance of revised work: Homework turned in late will not be graded
unless prior approval of the instructor has been obtained.

Attendance/Participation Policy: Attendance is required and students are expected to actively participate and engage
with the material during lectures.

Community Agreement/Classroom Conduct Policy: Community Agreement: Ground Rules for a Safe/Brave Space

- Be present (turn off cell phones and remove yourself from other distractions)
- Be respectful
- Assume good will
- Challenge with care - approach discussion as a "think out loud"
- Take space/make space
- Try not to make assumptions, seek to understand, not to judge
- Be open to challenges as an opportunity to learn something new
- Be open to different perspectives Debate the concepts not the person
- Be flexible when things don't work
- Share helpful tips
- Use preferred names and gender pronouns
- No side conversations
- Be willing to work together

Tentative Homework and Test Schedule:

Homework 1, Due Wednesday September 13

Homework 2, Due Friday September 27

TEST 1 -- Monday September 30

Homework 3, Due Friday October 11

Homework 4, Due Friday October 25

Homework 5, Due Friday November 8

TEST 2 -- Monday November 11

Homework 6, Due Friday November 22

Homework 7, Due Wednesday December 4

TEST 3 -- Friday December 6