Math 38, Spring 2023
Graph Theory

Sections

Brief Description

Week 1

1.1, 1.2

M: Basic definitions, examples of problems in graph theory.

W: Adjacency and incidence matrices, isomorphisms.

F: Paths, walks, cycles, components, cut-edges, cut-vertices, induced subgraphs.

Week 2

1.2, 1.3

M: Characterization of bipartite graphs, Eulerian graphs, vertex degrees, degree-sum formula.

W: Reconstruction conjecture. Extremal problems: largest minimum degree in disconnected graphs, largest bipartite subgraph,

F: More extremal problems: triangle-free graphs. Degree sequences, graphic sequences.

Week 3

1.4

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

W: Quiz 1.

F: No class on Apr 14  (Sergi away at a conference).

Week 4

2.1, 2.2

M: Trees and forests, characterizations of trees. Radius and diameter.

W:  Spanning trees, Enumeration of trees, Cayley’s formula, Prüfer code.

Th (X-hour): Counting spanning trees, deletion-contraction.

F: The matrix tree theorem. Decompositions and graceful labelings. Minimum spanning trees (Kruskal’s algorithm).

Week 5

2.3, 3.1

M: Shortest paths (Dijkstra’s algorithm), Breadth First Search. Matchings.

W: Maximal and maximum matchings, M-augmenting paths. Hall's theorem and consequences.

Th (X-hour): Quiz 2.

F: Min-max theorems, matchings and vertex covers,  independent sets and edge covers.

Week 6

3.1, 4.1, 4.2

M: Relating maximum matchings, minimum vertex covers, maximum independent sets, and minimum edge covers. Connectivity, vertex cuts.

W: Edge-connectivity, disconnecting sets, Whitney's theorem. 

F: Blocks, k-connected graphs.

Week 7

4.3, 5.1
 

M: Menger’s theorem, line graphs. Network flow problems, value of a flow.

W: Source/sink cuts. Ford-Fulkerson algorithm. Max-flow min-cut theorem.

Th (X-hour): Quiz 3.

F: Graph coloring.

Week 8

5.1, 5.3

M: Bounds on chromatic numbers, chromatic numbers of graphs constructed from smaller graphs.

W: The chromatic polynomial, the deletion-contraction recurrence.

F: Properties of the chromatic polynomial, simplicial elimination orderings, acyclic orientations.

Week 9

Chapter 6

M: Planar graphs, Euler's formula.

W: Kuratowski's theorem.

Th (X-hour): Quiz 4.

F:  Five and four color theorems. Final exam handed out.

Week 10

 Chapter 6

(No class on Memorial Day)

W: Final exam due.