Instructor: Robert Ellis  Office: E1 Bldg, Rm 105C  Email: 
Lectures 
TR 11:25am12:40pm  E1 Bldg. 106 
Office Hours 
MW 11am4:15pm, Walkin TR 1:504:30pm, By appointment 
Office phone 5675336 
Textbook 
West, Introduction to Graph Theory, 2nd edition, Prentice Hall  
Exam Schedule 
Exam 1: R Oct 22
454Key
553Key
Exam 2: T Nov 24 joint key Final: R Dec 10, 10:30am12:30pm 
Exams 1 & 2 will cover material including all returned homework to date 
First day handout (pdf) (course contract & exam schedule).
Department course syllabus. Math 454,
Math
553.
Concept map,
Graphs: What is the definition of a graph?
(Created using IHMC
CmapTools)
Concept map,
Walks: What are the kinds of walks
in a graph?
(Created using IHMC
CmapTools)
Sample exams from Fall 2005: Exam 1, Exam 2, Final Exam
Due Date  Math 454 Assignment  Math 553 Assignment 

R 8/27  Review handout of example notes for first part of Section 1.1 before lecture.  
T 9/1  Review 2nd handout of example notes, and fill in the blank examples, before lecture. This is the last notebook entry that will be modeled for you.  
R 9/3  Complete notebook entry for pages 1926 before lecture.  
R 9/3, 5pm Mailbox in E1 210 
HW 1. Section 1.1: 10, 12, 14, 18 (give the isomorphism); pick one of 26, 27; pick one of 35, 38.  HW 1. Section 1.1: 14, 18; pick one of 26, 27; pick one of 31, 34; pick one of 35, 38; 47 
R 9/10  Complete notebook entry for pages 2630 and 3438 up to Conjecture 1.3.12 before lecture.  
T 9/15  Complete notebook entry for pages 3847 before lecture.  
"Determine," "Show," etc. mean write a proof.  
T 9/15, 5pm Mailbox in E1 210 
HW 2. Section 1.2: 3, 15; 17 or 18; 20 or 22, 25 or 26, 38 or 40  HW 2. Section 1.2: 17 or 18; 20 or 22; 25 or 26; 38 or 40 
R 9/24, 5pm Mailbox in E1 210 
HW 3. Section 1.2: 8, 10 Section 1.3: 3, 7, 8, 12, 17, 26 or 32, 40 or 41 
HW 3. Section 1.2: 36 or 43 (see errata
for corrected problem statements)
Section 1.3: 12, 16 or 29, 26 or 32, 40 or 41 
R 9/24  Complete notebook entry for pages 5358 before lecture.  
T 9/29  Complete notebook entry for pages 5963 before lecture.  
R 10/1  Complete notebook entry for these pages before lecture. Math 454: pp.6773 Math 553: pp.6775 

F 10/2, 5pm Mailbox in E1 210 
HW 4. Section 1.3: 57 or 63 Section 1.4: 4, 5, 10 or 11, 19 or 20, 36 or 37 
HW 4. Section 1.3: 57 or 63
Section 1.4: 10 or 11, 14 or 25, 19 or 20, 36 or 37; choose one of 16 or 30 or 35 
R 10/8  Complete notebook entry for these pages before lecture. Math 454: pp.8188 Math 553: pp.8191 

T 10/13, 5pm Mailbox in E1 210 
HW 5. Section 2.1: 2, 17 or 18, 29, 35 or 36, 47, 62 or 64  HW 5. Section 2.1: 17 or 18, 29, 35 or 36, 47, 62 or 64, 72 
T 10/13  Complete notebook entry for these pages before lecture. Math 454: pp.9596 Math 553: pp.9596 

R 10/15  Complete notebook entry for these pages before lecture. Math 454: pp.97100 and 107113 Math 553: pp.97103 and 107113 

T 10/20, 5pm Mailbox in E1 210 
HW 6. Section 2.2: 6, 7, 15, 17, 24
Section 2.3: 2, 10 
HW 6. Section 2.2:
6, 7, 15, 17, 19 or 20, 28 or 29, 34 Section 2.3: 10 
T 10/27  Complete notebook entry for these pages before lecture. Math 454: pp.113115 Math 553: pp.113118 

R 10/29  Complete notebook entry for these pages before lecture. Math 454: pp.123129 Math 553: pp.123134 

R 10/29, 5pm Mailbox in E1 210 
HW 7. Section 2.3: 3, 13 or 14, 15, 18
(Reminder: we discussed a detailed reason behind 13 in lecture.) Section 3.1: 3, 8 
HW 7. Section 2.3: 13 or 14, 15, 17, 19, 26, 28
Section 3.1: 3, 8 
T 11/3  Complete notebook entry for these pages before lecture. Math 454: pp.136140 Math 553: pp.136145 

R 11/5  Complete notebook entry for these pages before lecture. Math 454: pp.149156 Math 553: pp.149157 

R 11/5 In class 
Exam 1 rewrite due. See email for rules. 

R 11/5, 5pm Mailbox in E1 210 
HW 8. Section 3.1: 9, 16, 19, 21, 32
Section 3.2: 2, 5 
HW 8. Section 3.1: 19, 24, 32, 43, 48, 49
Section 3.2: 4, 6, 7 
You should be able to trace through the Hungarian or Augmenting Path Algorithm on an exam (see slides link below).  
F 11/6, 5pm Mailbox in E1 210 
Homework amnesty deadline. See email for rules. 

R 11/12  Read the rest of Section 4.1, and read Section 4.2 through p.164.  
T 11/17 
Complete notebook entry for these pages before lecture. Math 454: pp.161170 Math 553: pp.161172 

T 11/17, 5pm Mailbox in E1 210 
HW 9. Section 3.3:
2, 4, 6, 10, 22
Section 4.1: 1, 4, 8 Also prove the following: the hypercube Q_{k} has connectivity k. 
HW 9. Section 3.3: 6, 7, 8, 12, 22
Section 4.1: 8, 10 Also prove the following: the hypercube Q_{k} has connectivity k. 
R 11/19 
Complete notebook entry for these pages before lecture. Math 454: pp.176184 Math 553: pp.176187 

F 12/4, 5pm Mailbox in E1 210 
HW 10. Section 4.1:
20, 27, 30 Section 4.2: 2, 3, 6 Section 4.3: 1, 2, 3 
HW 10. Section 4.1:
20, 27, 34
Section 4.2: 2, 6, 11 or 23 Section 4.3: 3, 5 or 10, 13 
Due Date  Math 454 Assignment  Math 553 Assignment 
page maintained by Robert Ellis / http://math.iit.edu/~rellis/