Office: Armstrong Hall 408H

Office Hours: MW 11:30am-12:30pm, and by appointment

Class Meetings: TuTh 11:30am-12:45pm in Armstrong Hall 309

No. | Date | Class Summary | Section(s) | Comments |

1 | Aug 17 | Introduction; Bridges and definitions | 1.1 | HW1 assigned. |

2 | Aug 22 | Cliques and Independent sets; important graphs; isomorphism | 1.1 | - |

3 | Aug 24 | Decompositions; Petersen graph | 1.1 | - |

4 | Aug 29 | Walks, trails, paths; components; cut-vertices and cut-edges | 1.2 | - |

5 | Aug 31 | Bipartite graphs; characterization | 1.2 | - |

6 | Sep 5 | Eulerian Circuits; Eulerian graph characterization | 1.2 | - |

7 | Sep 7 | Decomposing G into trails; degree-sum formula; hypercubes | 1.2,1.3 | HW1 due; HW2 assigned. |

8 | Sep 12 | Extremal Problems | 1.3 | - |

9 | Sep 14 | No class: WVU--China Graph Theory and Combinatorics Workshop | - | - |

10 | Sep 19 | Turan numbers; Mantel's theorem | 1.3 | - |

11 | Sep 21 | Degree sequences; Havel--Hakimi | 1.3 | HW2 due; HW3 assigned. |

12 | Sep 26 | Directed graphs; deBruijn cycles | 1.4 | - |

13 | Sep 28 | Trees: basic properties | 2.1 | - |

14 | Oct 3 | Prufer codes; deletion--contraction | 2.1 | - |

15 | Oct 5 | Midterm exam: coverage up to and including Sep 28 | - | HW3 due. Midterm (pdf) |

16 | Oct 10 | Deletion-contraction; Matchings | 2.2,3.1 | - |

17 | Oct 12 | Augmenting paths; Hall's Theorem | 3.1 | HW4 assigned. |

18 | Oct 17 | Vertex covers; Konig--Egervary Thm | 3.1 | - |

19 | Oct 19 | Tutte's Theorem | 3.3 | - |

20 | Oct 24 | Tutte's Theorem applications; connectivity | 3.3,4.1 | - |

21 | Oct 26 | Edge connectivity | 4.1 | HW5 assigned. |

22 | Oct 31 | Blocks; Block-cut point graph | 4.1 | - |

23 | Nov 2 | Ear Decompositions | 4.2 | - |

24 | Nov 7 | Menger's Theorem | 4.2 | - |

25 | Nov 9 | Flows; Ford--Fulkerson Algorithm | 4.3 | HW5 due. HW6 assigned. |

26 | Nov 14 | Vertex coloring; greedy coloring algorithm; interval graphs | 5.1 | - |

27 | Nov 16 | Brooks's Theorem | 5.1 | - |

28 | Nov 28 | Mycielski's Construction; Turan's Theorem | 5.2 | HW7 assigned (as of Nov. 23). HW6 due. |

29 | Nov 30 | Erdos--Stone--Simonovits Thm (w/o proof); Hajos and Hadwiger Conjectures | 5.2 | - |

30 | Dec 5 | Planar graphs: Kuratowski Thm; Euler's Formula | 6.1 | HW7 due. |

- | Dec 12 | Final Exam: Tue Dec 12, 8am to 10am | - | - |

milans@math.wvu.edu