Winter 2017

**Instructor:** Brendon Rhoades

**Instructor's Email:** bprhoades (at) math.ucsd.edu

**Instructor's Office:** 7250 APM

**Instructor's Office Hours:** 10:00-11:00am MWF

**Lecture Time:** 1:00-1:50pm MWF

**Lecture Room:** 109 CENTR

**TA:** Michelle Bodnar and Daniel Kroes

**TA's Email:** mbodnar (at) ucsd.edu and dkroes (at) ucsd.edu

**TA's Office:** 6434 APM (M. Bodnar) and 6414 APM (D. Kroes)

**TA's Office Hours:** 1:00-3:00 Tu and 10:00-12:00 W (M. Bodnar)
and 12:00-1:00 Tu and 12:00-1:00 F (D. Kroes)

**Discussion Time:** 4:00-4:50pm M, 5:00-5:50pm M, 6:00-6:50pm M

**Discussion Room:** 2206 WLH

**Final Exam Time:** Friday, 3/24/2017, 11:30am - 2:29pm

**Final Exam Room:** TBA

** Syllabus:**
Please read carefully.

Textbook for the graph theory portion of the course.

** Lectures:**

**1/9:** Administrivia. Chapter 1. Counting length n words from a size k
alphabet. Counting subsets of a size n set. The Bijection Principle.
Counting permutations of a size n set. Counting
size k ordered subsets of a size n set.

**1/11:** Chapter 1. Counting subsets. Binomial coefficients.
Pascal's Triangle. Counting lattice paths. Catalan numbers.

**1/13:** Chapter 2. Pigeonhole Principle. A number in the sequence
2017, 20172017, 201720172017, ... is divisible by 13.
If there are five points on a sphere, at least four of them lie on some
closed hemisphere. There are two people on Facebook with the same
number of friends.

**1/18:** Chapter 2. If the points of the plane are colored
red, blue, or green, there exists a rectangle in the plane with
monochromatic vertices. Chapter 3. The Binomial Theorem.
Some binomial coefficient identities.

**1/20:** Chapter 4. Domino tilings of a 2xn board.
The Fibonacci numbers. Explicit formula via linear algebra.

**1/23:** Chapter 2 of Wilson. Definition of a simple graph
(multiple edges, loops not allowed).
Definition of a graph (multiple edges, loops allowed). Graph isomorphism.
Union of graphs. Connected graphs and connected components.
Degree of a vertex. Degree sequences.

**1/25:** Chapter 2 of Wilson.
Handshake Lemma. Edge deletion. Vertex deletion.
Subgraphs. Edge contraction. Adjacency matrix A(G).
Incidence matrix M(G). Null graphs N_n, complete graphs K_n,
cycles C_n, paths P_n, wheels W_n.

**1/27:** Chapter 2 of Wilson. Bipartite graphs.
Complete bipartite graphs. Chapter 3 of Wilson.
Walks, trails, paths, and cycles. Every cycle in a bipartite
graph has even length.
Bounds on the number of edges in simple graphs with n vertices
and k components.

**1/30:** Chapter 3 of Wilson. Disconnecting sets and cutsets.
Edge connectivity lambda(G) of a connected graph G.
Eulerian trails and Eulerian graphs.

**2/1:** Chapter 3 of Wilson. A connected graph G is Eulerian
if and only if deg(v) is even for every vertex v.
Hamiltonian graphs and Hamiltonian cycles. Ore's Theorem: If G is a simple
graph with n > 2 vertices and, for any two non-adjacent vertices
u and v, we have deg(u) + deg(v) >= n, then G is Hamiltonian.
Dirac's Theorem: If G is a simple graph with n > 2 vertices
and deg(v) >= n/2 for all vertices v, then G is Hamiltonian.

**2/3:** Midterm 1.

**2/6:** Chapter 4 of Wilson. Forests and trees.
Characterizations of trees. Every tree has at least two leaves.
Anonymous course feedback.

**2/8:** Chapter 4 of Wilson. Labelled trees.
Cayley's Theorem: The number of trees on the vertex set
1, 2, ... , n is n^{n-2}. Spanning trees of graphs.
The Laplacian L(G) of a simple graph G. Statement of
the Matrix-Tree Theorem.

**2/10:** Chapter 4 of Wilson. The Greedy Algorithm.
Pessimistic government officials. Chapter 5 of Wilson.
Planar graphs. Planar drawings. K_5 and K_{3,3} are not planar.

**2/13:** Chapter 5 of Wilson. Graph homeomorphism. Kuratowski's
Theorem: A graph is planar if and only if no subgraph is homeomorphic
to K_5 or K_{3,3}. Faces of planar drawings and Euler's Formula
for connected planar graphs. Stereographic projection. Generalization
of Euler's Formula to possibly disconnected graphs.

**2/15:** Chapter 5 of Wilson. Application of Euler's Formula:
K_5 and K_{3,3} are not planar. Application of Euler's Formula: in
a planar graph G, there is a vertex of degree < 6.
Genus g surfaces. The genus g(G) of a graph G. We have g(K_5) = 1.

**2/17:** Chapter 5 of Wilson. The geometric dual G* of a plane
drawing G. G** = G. n* = f, m* = m, f* = n. Chapter 6 of Wilson.
k-colorable graphs. The chromatic number chi(G) of a graph G.
Examples.

**2/22:** Chapter 6 of Wilson. Degree bounds on the chromatic number
of graphs. Statement of Brooks' Theorem. The 6-color theorem for
simple planar graphs. The 5-color theorem for simple planar graphs.
Statement of the 4-color theorem for simple planar graphs.
The Art Gallery Problem.

**2/24:** Chapter 6 of Wilson. The chromatic polynomial P_G(k) of
a graph G. Chromatic polynomials of null graphs, complete graphs, and paths.
Deletion-Contraction. Applications: The chromatic polynomial is indeed
a polynomial, with degree equal to the number of vertices.

**2/27:** Chapter 6 of Wilson. The chromatic polynomial P_G(k)
has the form G = k^n - m k^(n-1) + ... , where G has n vertices and m
edges. The chromatic polynomial is an incomplete isomorphism invariant
of simple graphs. Chapter 7 of Wilson. Directed graphs: vertices and arcs.
Simple digraphs. Examples of digraphs.

**3/1:** Chapter 7 of Wilson. The underlying graph of a digraph.
Connectivity and strong connectivity of digraphs. Orientable graphs.
A graph G is orientable iff every edge of G is contained in at least one
cycle.

**3/3:** Midterm 2.

**3/6:** Chapter 7 of Wilson. The in-degree and out-degree of vertices
in digrahps. Handshake dilemma. The adjacency matrix M of a digraph D.
Eulerian diagraphs. Euler's Theorem for digraphs.

**3/8:** Prof. Rhoades was in Pasadena. Prof. Buss lectured
on Hamiltonian and semi-Hamiltonian digraphs. Tournaments.
Every non-Hamiltonian tournament is semi-Hamiltonian. Every
strongly connected tournament is Hamiltonian.

**3/10:** Chapter 8 of Wilson. Hall's Marriage Problem.
Marriage Condition. Hall's Marriage Theorem. Matchings and perfect
matchings in graphs. Complete matchings in bipartite graphs.

**3/13:** Chapter 8 of Wilson. Transversals of lists (S_1, ... , S_m)
of sets. Hall's Theorem for transversals; alternative proof.
Latin rectangles and Latin squares. Every Latin rectangle can be
extended to a Latin square.

**3/15:** Clutters (C_1, ... , C_m) of sets.
Sperner's Theorem. Proof of Sperner's Theorem via the LYM inequality.

**3/17:** Review.

** Homework Assignments: **

Homework 1, due 1/18/2017.
Solutions.

Homework 2, due 1/25/2017.
Solutions.

Homework 3, due 2/1/2017.
Solutions.

Homework 4, due 2/15/2017.
Solutions.

Homework 5, due 2/22/2017.
Solutions.

Homework 6, due 3/1/2017.
Solutions.

Homework 7, due 3/15/2017.

** Midterms: **

Practice Midterm 1 and
Solutions.

Midterm 1 and
Solutions.

Score Distribution: 95, 93, 91, 91, 90, 90, 88, 88,
87, 86, 85, 83, 83, 80, 77, 77, 75, 74, 74, 73, 72,
70, 69, 69, 68, 68, 67, 66, 66, 66, 64, 63, 62,
61, 60, 60, 58, 57, 56, 56, 56, 55, 54, 54, 54, 54, 54,
53, 53, 51, 48, 48, 47, 47, 46, 46, 46, 45, 45, 43, 42, 41,
39, 38, 38, 36, 36, 35, 31, 29, 28, 28, 27, 21, 19, 13.

Midterm 2 and
Solutions.

Score Distribution: 100, 97, 97, 94, 92, 90, 90, 87, 86,
85, 85, 85, 85, 85, 82, 82, 82, 81, 80, 80, 80, 80, 79,
78, 78, 78, 77, 77, 75, 75, 75, 75, 73, 72, 72, 70, 70, 70,
66, 66, 65, 65, 62, 62, 62, 60, 60, 60, 58, 57, 57, 56, 56, 56,
54, 54, 53, 50, 48, 42, 42, 41, 40, 39, 36, 34, 32, 30, 27,
26, 26, 22, 17, 6.