Weeks 1 & 2 — Introduction (3 classes)

9/1, pp. 1–12: graph, vertex, edge, finite graph, multiple edges, loop, simple graph, adjacent, neighbors, incident, endpoint, degree, degree sum, isolated vertex, leaf, end vertex, degree sequence, graphic, Havel-Hakimi algorithm

• Syllabus discussion.
• What is a graph?
• How to describe a graph.
• Degree sequence of a graph.
• Theorem 1.1.2.

9/3 pp. 13–15 & 19–23: path graph P_n, cycle C_n, complete graph K_n, bipartite graph, complete bipartite graph K_m,n, wheel graph W_n, star graph St_n, cube graph, Petersen graph, Grotzsch graph, Platonic solid, Schlegel diagram, Tetrahedron, Cube, Octahedron, Dodecahedron, Icosahedron

• Proof of Theorem 1.1.2.
• A dictionary of graphs.
• Schlegel diagrams of Platonic solids.

9/8 pp. 16–18 & 24: equal graphs, isomorphic graphs, disjoint union, union, graph complement, self-complementary graph, subgraph, induced subgraph, proper subgraph,

• When are two graphs the same?
• Smaller graphs from larger graphs.
• Groupwork on definitions.

9/10: Discussion of Homework 2

          Weeks 3 & 4 — Connectivity (3 classes)

9/15: pp. 25–28: path in G from a to b, connected graph, connected component, tree, forest,

• Groupwork discussion.
• Connected graphs and connected components
• Theorem 1.3.1
• 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.

9/17: pp. 29–34: k-connected, connectivity κ(G), separating set, cut vertex, k-edge connected, edge connectivity λ(G), disconnecting set, bridge, minimum degree δ(G), maximum degree Δ(G),

• Trees and forests.
• Theorems 1.3.2, 1.3.3, and 1.3.5.
• k-connectivity and k-edge-connectivity

9/22: pp. 35–39: block, H-path, ear, ear decomposition

• Theorems 2.4.1 and 3.2.1
• κ(G) ≤ λ(G) ≤ δ(G)
• Discussion of minimum vs. minimal
• Properties of blocks
• Whitney and Menger theorems
• Characterization of 2-connectivity

          Week 4 — Graph Statistics (2 classes)

9/24: pp. 40–43: vertex cover, clique number ω(G), girth g(G), distance d(x,y), diameter diam(G), independent set, independence number α(G), vertex cover, size of minimum vertex cover β(G),

• Cliques, girth.
• Worksheet on statistics of graphs

10/1: Discussion of Homework 4

10/6:

• Discussion of worksheet on statistics of graphs

          Weeks 6 & 7 — Coloring graphs (2 classes)

10/8: pp. 44–48: (proper) coloring, chromatic number, critical graph

• 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.
• Critical graphs, Thms 2.1.1-2.1.2.
• Critical graphs, Thms 2.1.3-2.1.4.
• Groupwork: the chromatic number of Gr.

10/13: pp. 49–55 bipartite, edge coloring, proper edge coloring, edge chromatic number, snark, turning trick

• Bipartite graphs, Thm 2.1.6.
• edge coloring, proper edge coloring, edge chromatic number.
• Thms 2.2.1-2.2.2
• Snarks
• Turning trick.
• Line graph of a graph

10/15: Discussion of Homework 6

10/22: Question and Answer session

10/24: Midterm Exam

          Weeks 9–10 — Cycles and Circuits (3 classes)

10/27: pp. 56–63 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/29: pp. 64–72 (closed) knight's tour, walk, trail, path, open, closed, circuit, cycle, loop, Eulerian circuit, Eulerian Trail

• Knight's tours.
• Vocabulary of pseudographs.
• Eulerian circuits.

11/3: pp. 73–83 Eulerian circuit, Eulerian Trail, sequence, binary sequence, de Bruijn sequence, de Bruijn graph

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

          Weeks 10–11 — Planarity (3 classes)

11/5: pp. 84–92 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
• Maps, normal maps.
• Four Color Theorem (not proved).
• History of the four color theorem.

11/10: pp. 93–102 map, normal map, map coloring, deleting a vertex (G\v), deleting an edge (G\e), edge contraction, subdivision, minor

• Six Color Theorem (proved).
• Five Color Theorem (proved).
• Modifications of graphs.
• Kuratowski's Theorem.

11/12: Discussion of Homework 8

          Weeks 12-14 -- Algorithms (4 classes)

11/17: pp. 103–110 matching, maximal matching, maximum matching, Hungarian Algorithm

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

11/19: pp. 111–117 stable matching, stable matching algorithm

• Stable matchings
• Stable matching algorithm
• Applications to medical school choice
• Proof of male-optimality in the Gale-Shapley algorithm
• Counting matchings in a bipartite graph

11/24: Peer Review of Course Projects

12/1: pp. 118–128 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
• Max Flow / Min Cut Algorithm

12/3: pp. 129–136

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

12/8: Discussion of Homework 10

12/10: Question and Answer Session

          Finals Week

EXAM 2, Tuesday, December 15 from 4–6pm

Other fun things in Graph Theory: