# Math 180: General Course Outline

## Catalog Description

180. Graph Theory. (4) Lecture, three hours; discussion, one hour. Requisites: courses 31A, 31B, and 61. Strongly recommended preparation: 115A. Graphs and trees. Planarity, graph colorings. Set systems. Ramsey theory. Random graphs. Linear Algebra methods. Ideal for students in computer science and engineering. P/NP or letter grading.

## Course Information:

The following schedule, with textbook sections and topics, is based on 25 lectures. The remaining classroom meetings are for leeway, reviews, and midterm exams. These are scheduled by the individual instructor. Often there are reviews and midterm exams about the beginning of the fourth and eighth weeks of instruction, plus reviews for the final exam.

## Textbook

J. Matousek and J. Nesetril, Invitation to Discrete Mathematics, 2nd Ed., Oxford

Outline update: I. Pak, 12/15

## Schedule of Lectures

Lecture Section Topics

1

1-3

Basic counting methods (induction, pigeonhole principle).

2

4.1 - 4.3

Graphs, subgraphs, graph isomorphism. Connectivity. Score.

3

4.4 - 4.7

Eulerian graphs, diagraphs. Hamiltonian cycles. 2-connected graphs.

4

5

Trees, their characterizations, isomorphism. Minimal spanning tree problem.

5

6

Planar graphs. Euler's formula. Examples of non-planar graphs. Five color theorem.

6

7

Sperner's Lemma. Set systems. Sperner's theorem via LYM inequality.

7

10, 9.4

Probabilistic method (expectation, independence). 2-Colorings. Random sorting. Turan's theorem.

8

11

Ramsey's theorem (upper bound, lower bound).

9

13

Linear algebra methods. Cycle space of a graph. Graham-Pollak theorem. Matrix tree theorem.

10

13.6, 9

Probabilistic checking. Finite projective planes. Applications to graphs with no 4-cycles.