9/2: graph isomorphism, isomorphic graphs, subgraph, induced subgraph

• Theorem 1.1.2.
• When are two graphs the same?
• Smaller graphs from larger graphs.

9/4: complete graph K_n, bipartite graph K_m,n, Petersen graph, cycle, path, wheel, star, Tetrahedron, Cube, Octahedron, Dodecahedron, Icosahedron, subgraph, induced subgraph, complement, Platonic solid, Schlegel diagram

• A dictionary of graphs.
• Schlegel diagrams of Platonic solids.

          Week 3 -- Connectivity (2 classes)

9/9: path in G from a to b, connected graph, connected component, tree, forest

• Connected graphs, Thms 1.3.1-1.3.3.
• Lemma A. If there is a path from a to b in G and a path from b to c in G, then there is a path from a to c in G.
• Remark: If you remove an edge from a cycle, the remaining graph is connected.
• Lemma B. Let G be a connected graph. Let C be a cycle contained in G. Let e be any edge in C. Then the graph G\e is connected.
• Introduction to trees and forests.

9/11: deleting a vertex (G\v), deleting an edge (G\e), proper subgraph, self-complementary graph, bridge, cut-vertex, k-connected, connectivity κ(G), cut vertex, separating set, k-edge connected, edge connectivity λ(G), bridge, disconnecting set, minimum degree δ(G), maximum degree Δ(G), edge cut, vertex cover, clique number ω(G), girth g(G)

• Deleting a vertex, deleting an edge
• Connectivity definitions
• λ(G) <= δ(G).
• κ(G) <= λ(G).
• Cliques, girth.
• Worksheet on statistics of graphs

9/16: Discussion of Homework 4

• Conditions under which a graph may be self-complementary

          Weeks 4 and 5 -- Coloring graphs (3 classes)

9/18: diameter diam(G), distance d(x,y), (proper) coloring, chromatic number

• Discussion of maximum vs. maximal.
• Proper colorings, chromatic number.
• Lemma C. If H is a subgraph of G, and chi(H)=k, then chi(G)>=k.
• Cliques and their relation to chromatic number.

9/23: critical graph, bipartite, k-partite

• Critical graphs, Thms 2.1.1-2.1.2.
• Critical graphs, Thms 2.1.3-2.1.4.
• Bipartite graphs, Thm 2.1.6.
• Groupwork: the chromatic number of Gr.

9/25: proper edge coloring, edge chromatic number, snark, turning trick

• An edge coloring of a graph.
• Turning trick.
• Line graph of a graph

          Weeks 6-8 -- Cycles and Circuits (4 classes)

10/2: Decomposition, Hamiltonian cycle

• Decomposition of a graph into smaller graphs
• A snark has no Hamiltonian cycle.
• If G has a Hamiltonian cycle, then kappa(G) >= 2 and kappa'(G) >= 2.
• Hamiltonian cycle decomposition of K_n.

10/7: Discussion of Homework 7

10/16: (closed) knight's tour, walk, trail, path, open, closed, circuit, cycle, loop

• Knight's tours.
• Vocabulary of pseudographs.

10/21: Eulerian circuit, Eulerian Trail, sequence, binary sequence, de Bruijn sequence, de Bruijn graph

• Eulerian circuits.
• Thm 3.1.2. Even degrees implies Eulerian.
• Eulerian Trails.
• de Bruijn sequences.

10/23: Question and Answer session

10/28: Midterm Exam

          Weeks 10-11 -- Planarity (4 classes)

10/30: 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.

11/4: map, normal map, map coloring,

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

11/6: vertex deletion, edge deletion, edge contraction, subdivision, minor, crossing number

• Modifications of graphs.
• Kuratowski's Theorem.
• Crossing number of a graph.

11/11: thickness, genus of a graph, algorithm, matching, maximal matching, maximum matching, Hungarian Algorithm

• Thickness of a graph.
• Genus of a graph.
• Euler's formula for surfaces of higher genus.
• What is an algorithm?

          Weeks 12-16 -- Algorithms (5 classes)

11/13: directed graph, network, capacity of an edge, flow, maximum flow, st-edge cut, minimum cut

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

11/18: Discussion of Homework 13

11/20:

• Max Flow / Min Cut Algorithm
• Transshipment problems.
• Applying Max Flow / Min Cut to solve transshipment problems.
• Dynamic Networks

11/25: Peer Review of Course Projects

12/2: matching, maximal matching, maximum matching, Hungarian Algorithm

• Matchings
• Maximum Matchings
• Hungarian Algorithm

12/4: stable matching, stable matching algorithm

• Applying Max Flow / Min Cut to solve maximum matching.
• Stable matchings
• Stable matching algorithm
• Applications to medical school choice

12/9:

• Proof of male-optimality in the Gale-Shapley algorithm
• Research Topic: Counting perfect matchings

12/11: Discussion of Homework 16

12/16: Question and Answer Session

EXAM 2, Thursday, December 18 from 6:15-8:15pm

Other fun things in Graph Theory: