1/25: adjacent, incident, neighbors, degree, degree sequence, graphic, isolated vertex, leaf

• How to describe a graph.
• Degree sequence of a graph.

1/26: graph isomorphism, isomorphic graphs

• Discussion of Homework 1B.
• When are two graphs the same?

1/27: complete graph K_n, bipartite graph K_m,n, Petersen graph, cycle, path

• Proof of Theorem 1.1.2.
• A dictionary of graphs.

          Week 2 -- Trees

1/30: wheel, star, subgraph, induced subgraph, connected graph, tree, forest

• Smaller graphs from larger graphs.
• Connected graphs, Thms 1.3.1-1.3.3.
• Introduction to trees and forests.

2/1: labeled tree, unlabeled tree

• More trees and forests.
• Counting unlabeled trees and labeled trees: Cayley's Theorem.

2/3: root, rooted tree, decision tree, spanning subgraph, spanning tree, k-regular, k-factor, 1-factor, perfect matching

• Discussion of Homework 2A.
• More trees and forests.

          Week 3 -- Coloring

2/6: (proper) coloring, chromatic number, clique number, girth, distance between vertices, triangle inequality, diameter

• Proper colorings, chromatic number.
• Lemma A. If H is a subgraph of G, and chi(H)=k, then chi(G)>=k.
• Statistics on graphs.

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

• Critical graphs, Thms 2.1.1-2.1.4.
• Bipartite graphs, Thm 2.1.6.

2/10: edge coloring, edge chromatic number, snark, perfect matching decomposition

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

          Week 4

2/13: decomposition, Hamiltonian cycle, Traveling Salesman Problem

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

2/15: Platonic solid, Schlegel diagram, Graphs: Tetrahedron, Cube, Octahedron, Dodecahedron, Icosahedron

• Schlegel diagrams of Platonic solids.
• Worksheet on statistics of graphs.

2/17: walk, trail, path, open, closed, circuit, cycle, loop, lune, Eulerian circuit

• Hamiltonian cycle decomposition of K_n.
• Vocabulary of pseudographs.
• Eulerian circuits.

          Week 5

2/20: Eulerian Trail

• 3.1.2 even degrees implies Eulerian.
• Eulerian Trails.

2/22: Question and Answer Session

• Lemma B. If G is a connected graph, and a subgraph C is a cycle, and e is any edge in C, then G\e is connected.

2/24: Ramsey number, independent set, independence number

• Ramsey Theory.
• Independent Sets.

4/7: algorithm, edge weighting

• What is an algorithm?
• Spanning Tree Algorithm

          Week 11 -- Minimum Weight Spanning Tree

4/10:

• Kruskal's Minimum Weight Spanning Tree Algorithm

4/12: Erdös Video

4/14: NO CLASS

          Week 12 -- Algorithms

4/17: NO CLASS

4/19:

• Traveling Salesman Problem
• A 2-approximation algorithm for the TSP

4/21:

• Maximum Matchings
• Hungarian Algorithm

          Week 13 -- Matchings

4/24:

• When do perfect matchings exist?
• Hall's Marriage Theorem

4/26:

• Counting matchings, other subgraphs, spanning trees.
• (Sections 5.1 and 5.3)

4/28:

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

          Week 14 -- Max Flow / Min Cut

5/1: network, capacity of an edge, flow, maximum flow, edge cut, minimum cut, augmenting path

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

5/3: Ford-Fulkerson algorithm

• Max Flow / Min Cut Algorithm

5/5: Transshipment

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

          Week 15 -- Wrap-Up

5/8: Linear Program, dual program, feasible region, optimal vector, optimal value