Math 38, Spring 2025
Graph Theory

Week
 

Sections

Class Materials

03/31 - 04/04 

1.1, 1.2

First day of class 04/01.

Textbook reading: pg. 1- 13 & 19 - 24

1.1: Basic definitions, examples of problems in graph theory. Adjacency and incidence matrices, isomorphisms.

1.2: Paths, walks, cycles, components

04/07 - 04/11

1.2, 1.3

04/07 - HW #0 Due

Textbook reading: 19 - 28 & 34 - 38

1.2: components, cut-edges, cut-vertices. Induced subgraphs, characterization of bipartite graphs, Eulerian graphs.

1.3: Vertex degrees, degree-sum formula, reconstruction conjecture. Extremal problems: largest minimum degree in disconnected graphs,  largest bipartite subgraph.

*Last day to drop the course without "W"

04/14 - 04/18

1.3,1.4

04/14 - HW #1 Due

04/17  (X-hour): Quiz 1.

1.3: Triangle-free graphs. Degree sequences, graphic sequences. Directed graphs. 

Play around with Havel-Hakimi algorithm here: https://d3gt.com/unit.html?havel-hakimi Links to an external site.

1.4: Directed graphs. Connected digraphs, Eulerian digraphs, De Bruijn cycles. Orientations and tournaments.

04/21 - 04/25

2.1, 2.2

04/21 - HW #2 Due

04/28 - 05/02

2.3, 3.1

04/28 - HW #3 Due

05/02  (X-hour): Quiz 2.

05/05 - 05/09

3.1, 4.1

05/05 - HW #4 Due

05/12 - 05/16

4.2, 4.3
 

05/12 - HW #5 Due

05/16 (X-hour): Quiz 3.

05/19 - 05/23

5.1, 5.3

05/19 - HW #6 Due

*05/21 Final course drop date

05/26 - 05/30

Chapter 6

05/26 - HW #7 Due

05/30 (X-hour): Quiz 4.

06/02 - 06/06

 Chapter 6

*06/04 - Last day of class (No class on Thursday)

*06/05 - Final exam released