New definitions are in bold and key topics covered are in a bulleted list.
This schedule is approximate and subject to change!

          Week 1 -- Introduction

1/28: graph, vertex, edge, finite graph, infinite graph, multiple edges, multigraph, loop, pseudograph, simple graph

• Syllabus discussion.
• What is a graph?

          Week 3 -- Connectivity and Graph Statistics

2/11: spanning subgraph, spanning tree, girth g(G), diameter diam(G), distance d(x,y)

• Proof of theorem 1.3.5

2/12: Discussion of Homework 3A

2/13: self-complementary graph, connected, disconnected, (connected) component, k-connected, connectivity κ(G), cut vertex, separating set, vertex cut, cutset, k-edge connected, edge connectivity λ(G), bridge, disconnecting set

• Continued discussion of Homework 3A
• Conditions under which a graph may be self-complementary
• Connectivity definitions

2/15: minimum degree δ(G), maximum degree Δ(G), edge cut, vertex cover, independent set

• Bridges and thms. 2.4.1, 3.2.1.
• λ(G) <= δ(G).
• Edge cuts.
• κ(G) <= λ(G).

          Week 4 -- Connectivity and Graph Statistics

2/18: block, block graph, independent set, independence number α(G), vertex cover, size of minimum vertex cover β(G), clique number ω(G)

• Properties of blocks.
• Independent set and independence number of a graph.
• Vertex covers.
• Cliques.

2/19: Discussion of Homework 4A

• Worksheet on statistics of graphs

2/20: H-path, ear, ear decomposition

• Mini-Menger and Menger's Theorem.
• Ear decomposition.
• 2-connectedness equivalences.

2/22: Wrap-up loose end day

• Questions from 2/4
• Graph statistics worksheet

          Week 5 -- Coloring

2/25: Question and Answer Session

2/26: EXAM 1

2/27: (proper) coloring, chromatic number

• Proper colorings, chromatic number.
• Lemma B. If H is a subgraph of G, and chi(H)=k, then chi(G)>=k.
• Critical graphs, Thms 2.1.1-2.1.2.

2/29: removing a vertex (G\v), removing an edge (G\e), proper subgraph, critical graph, bipartite, k-partite

• Critical graphs, Thms 2.1.3-2.1.4.
• Bipartite graphs, Thm 2.1.6.
• Statistics on Graphs, Chart II.

          Week 6 -- The Chromatic Polynomial

3/3: chromatic polynomial P_G(λ)

• Groupwork: the chromatic number of Gr.
• Chromatic polynomial of a graph
• Examples of P_G(λ)

3/4: Discussion of Homework 6A

3/5: edge deletion G\e, edge contraction G/e

• Relationship between a graph's chromatic polynomial and its chromatic number.
• Coloring a pseudograph
• Edge contraction
• Calculating P_G(λ) through deletion-contraction

3/7: acyclic orientation of a graph

• Interesting properties of the chromatic polynomial.
• Acyclic orientation of a graph.
• Tournament

          Week 7 -- Coloring Edges and Decompositions

3/10: proper edge coloring, edge chromatic number, snark

• An edge coloring of a graph.
• Turning trick.
• Thinking of matchings of K_2n as a Tournament.

3/11: Discussion of Homework 7A

3/12: Line graph L(G), Ramsey number

• Line graph of a graph
• Ramsey Theory.

3/14: decomposition, Hamiltonian cycle

• A snark has no Hamiltonian cycle.
• Interesting properties of Hamiltonian cycles in graphs.

          Week 8 -- Cycles and Circuits

3/17: Traveling Salesman Problem, (closed) knight's tour

• Hamiltonian cycle decomposition of K_n.
• If G has a Hamiltonian cycle, then kappa(G) >= 2 and kappa'(G) >= 2.
• Knight's tours.

3/18: Discussion of Homework 8A

3/19: walk, trail, path, open, closed, circuit, cycle, loop, lune, Eulerian circuit

• Vocabulary of pseudographs.
• Eulerian circuits.
• Thm 3.1.2. Even degrees implies Eulerian.

          Week 9 -- Eulerian Applications, Planarity

3/31: Eulerian Trail, sequence, binary sequence, de Bruijn sequence, de Bruijn graph

• Eulerian Trails.
• de Bruijn sequences.

4/1: Discussion of Homework 9A

4/4: drawing, simple curve, plane drawing, plane graph, planar graph, region, face, outside face, maximal planar, dual graph

• Planar graphs.
• Euler's Formula.
• Maximal planar graphs.
• dual graph, self-dual graph

4/9: vertex deletion, edge deletion, edge contraction, vertex splitting, expansion, subdivision, minor, crossing number

• Modifications of graphs.
• Kuratowski's Theorem.

          Week 10 -- Planarity

4/7: Question and Answer Session

4/8: EXAM 2

4/9: map, normal map, map coloring,

• Maps, normal maps.
• Four Color Theorem (not proved).
• History of the four color theorem.
• Six Color Theorem (proved).

4/11: crossing number of a graph

• Five Color Theorem (proved).
• Crossing number of a graph.

          Weeks 11 and 12 -- Matrices

4/14: thickness, genus of a graph

• Thickness of a graph.
• Genus of a graph.
• Euler's formula for surfaces of higher genus.

4/15: Discussion of Homework 11A

4/16: unoriented incidence matrix, oriented incidence matrix, adjacency matrix, directed graph

• Directed graph.
• Incidence matrix.
• Adjacency matrix.

4/18: No class; Passover

4/21: No class; Passover

4/22: Erdös Video

4/23: eigenvalue, eigenvector, and spectrum of a graph, vertex weighting

• Graph interpretation of matrix multiplication.
• Eigenvalues and eigenvectors of a matrix.
• Thm. A d-regular graph has lambda=d as an eigenvalue.

4/25: Laplacian matrix

• Powers of the adjacency matrix.
• The Matrix Tree Theorem
• Proof of Cayley's Formula

          Weeks 13 and 14 -- Algorithms

4/28:

• What is an algorithm?
• Maximum Matchings
• Hungarian Algorithm

4/29: Group Discussion of Course Projects

4/30:

• Stable matchings
• Stable matching algorithm
• Applications to medical school choice

5/2:

• Max Flow / Min Cut Introduction
• Ford-Fulkerson theorem

5/5:

• Max Flow / Min Cut Algorithm

5/6: Discussion of Homework 14A

5/7:

• Applying Max Flow / Min Cut to solve maximum matching.
• Transshipment problems.
• Applying Max Flow / Min Cut to solve transshipment problems.

5/9: Question and Answer Session

          Finals Week

EXAM 3, Monday, May 12 from 4:30-6:30pm in FA 212

Other fun things in Graph Theory: